Phoenix and Earthquake solution codeforces – Phoenix’s homeland, the Fire Nation had nn cities that were connected by mm roads 2021

  Phoenix and Earthquake solution codeforces

Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces

Phoenix’s homeland, the Fire Nation had nn cities that were connected by mm roads, but the roads were all destroyed by an earthquake. The Fire Nation wishes to repair n1n−1 of these roads so that all the cities are connected again.

The ii-th city has aiai tons of asphalt. xx tons of asphalt are used up when repairing a road, and to repair a road between ii and jj, cities ii and jj must have at least xx tons of asphalt between them. In other words, if city ii had aiai tons of asphalt and city jj had ajaj tons, there would remain ai+ajxai+aj−x tons after repairing the road between them. Asphalt can be moved between cities if the road between them is already repaired.

Please determine if it is possible to connect all the cities, and if so, output any sequence of roads to repair.

Input   Phoenix and Earthquake solution codeforces

The first line contains integers nnmm, and xx (2n31052≤n≤3⋅105n1m3105n−1≤m≤3⋅1051x1091≤x≤109) — the number of cities, number of roads, and amount of asphalt needed to repair one road.

The next line contains nn space-separated integer aiai (0ai1090≤ai≤109) — the amount of asphalt initially at city ii.

The next mm lines contains two integers xixi and yiyi (xiyixi≠yi1xi,yin1≤xi,yi≤n) — the cities connected by the ii-th road. It is guaranteed that there is at most one road between each pair of cities, and that the city was originally connected before the earthquake.

Output   Phoenix and Earthquake solution codeforces

If it is not possible to connect all the cities, print NO. Otherwise, print YES followed by n1n−1 integers e1,e2,,en1e1,e2,…,en−1, the order in which the roads should be repaired. eiei is the index of the ii-th road to repair. If there are multiple solutions, print any.

Examples Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces

input

Copy
5 4 1
0 0 0 4 0
1 2
2 3
3 4
4 5

output Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces

Copy
YES
3
2
1
4

input   Phoenix and Earthquake solution codeforces

Copy
2 1 2
1 1
1 2

output   Phoenix and Earthquake solution codeforces

Copy
YES
1

input   Phoenix and Earthquake solution codeforces

Copy
2 1 2
0 1
1 2

output

Copy
NO

input

Copy
5 6 5
0 9 4 0 10
1 2
1 3
2 3
3 4
1 4
4 5

output

Copy
YES
6
4
1
2
Note

In the first example, the roads are repaired in the following order:

  • Road 33 is repaired, connecting cities 33 and 44. City 44 originally had 44 tons of asphalt. After this road is constructed, 33 tons remain.
  • Road 22 is repaired, connecting cities 22 and 33. The asphalt from city 44 can be transported to city 33 and used for the road. 22 tons remain.
  • Road 11 is repaired, connecting cities 11 and 22. The asphalt is transported to city 22 and used for the road. 11 ton remain.
  • Road 44 is repaired, connecting cities 44 and 55. The asphalt is transported to city 44 and used for the road. No asphalt remains.

All the cities are now connected.In the second example, cities 11 and 22 use all their asphalt together to build the road. They each have 11 ton, so together they have 22 tons, which is enough.

In the third example, there isn’t enough asphalt to connect cities 11 and 22.

GNU C++ 17 (64)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m;
ll x, s = 0;
cin >> n >> m >> x;
vector<ll> a(n+1);
for(int i = 1; i <= n; ++i) {
cin >> a[i];
s += a[i];
}
if((n-1)*x > s) return cout << "NO\n", 0;

vector<vector<pair<int, int>>> G(n+1);
vector<bool> seen(n+1, false);
for(int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
G[x].emplace_back(y, i);
G[y].emplace_back(x, i);
}
cout << "YES\n";

vector<int> order, tree, p, rev_ans;
order.push_back(1);
seen[1] = true;
for(int i = 0; i < n; ++i) {
for(auto [j, e] : G[order[i]]) if(!seen[j]) {
seen[j] = true;
order.push_back(j);
tree.push_back(e);
p.push_back(order[i]);
}
}
for(int i = 1; i < n; ++i) {
int u = order[n-i], v = p[n-1-i], e = tree[n-1-i];
if(a[u]+a[v] < x) rev_ans.push_back(e);
else {
cout << e << '\n';
a[v] += a[u] - x;
}
}
reverse(rev_ans.begin(), rev_ans.end());
for(int e : rev_ans) cout << e << '\n';

return 0;
}

JAVA 11

import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.System.arraycopy;
import static java.lang.System.exit;
import static java.util.Arrays.copyOf;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
import java.util.StringTokenizer;

public class F {

static class IntList {

int data[] = new int[3];
int size = 0;

boolean isEmpty() {
return size == 0;
}

int size() {
return size;
}

int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return data[index];
}

void clear() {
size = 0;
}

void set(int index, int value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
data[index] = value;
}

void expand() {
if (size >= data.length) {
data = copyOf(data, (data.length << 1) + 1);
}
}

void insert(int index, int value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
expand();
arraycopy(data, index, data, index + 1, size++ - index);
data[index] = value;
}

int delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
int value = data[index];
arraycopy(data, index + 1, data, index, --size - index);
return value;
}

void push(int value) {
expand();
data[size++] = value;
}

int pop() {
if (size == 0) {
throw new NoSuchElementException();
}
return data[--size];
}

void unshift(int value) {
expand();
arraycopy(data, 0, data, 1, size++);
data[0] = value;
}

int shift() {
if (size == 0) {
throw new NoSuchElementException();
}
int value = data[0];
arraycopy(data, 1, data, 0, --size);
return value;
}
}

static int dsuGet(int dsu[], int i) {
return dsu[i] == i ? i : (dsu[i] = dsuGet(dsu, dsu[i]));
}

static boolean dsuMerge(int dsu[], int i, int j) {
i = dsuGet(dsu, i);
j = dsuGet(dsu, j);
if (i == j) {
return false;
}
dsu[j] = i;
return true;
}

static void solve() throws Exception {
int n = scanInt(), m = scanInt(), x = scanInt();
long a[] = new long[n];
long sum = 0;
for (int i = 0; i < n; i++) {
a[i] = scanInt();
sum += a[i];
}
int u[] = new int[m], v[] = new int[m];
for (int i = 0; i < m; i++) {
u[i] = scanInt() - 1;
v[i] = scanInt() - 1;
}
if (sum < (long) x * (n - 1)) {
out.println("NO");
return;
}
int dsu[] = new int[n];
for (int i = 0; i < n; i++) {
dsu[i] = i;
}
IntList roads[] = new IntList[n];
for (int i = 0; i < n; i++) {
roads[i] = new IntList();
}
for (int i = 0; i < m; i++) {
roads[u[i]].push(i);
roads[v[i]].push(i);
}
int allRoadsPtr = 0;
int stack[] = new int[2 * n - 1], stackSize = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= x) {
stack[stackSize++] = i;
}
}
out.println("YES");
i: for (int i = 0; i < n - 1; i++) {
while (stackSize > 0) {
int cur = stack[--stackSize];
if (dsuGet(dsu, cur) != cur || a[cur] < x) {
continue;
}
a[cur] -= x;
while (true) {
int r = roads[cur].data[--roads[cur].size];
int uu = dsuGet(dsu, u[r]), vv = dsuGet(dsu, v[r]);
if (uu != vv) {
out.println(r + 1);
dsuMerge(dsu, uu, vv);
a[uu] += a[vv];
if (roads[uu].size < roads[vv].size) {
IntList tt = roads[uu];
roads[uu] = roads[vv];
roads[vv] = tt;
}
for (int j = 0; j < roads[vv].size; j++) {
roads[uu].push(roads[vv].data[j]);
}
if (a[uu] >= x) {
stack[stackSize++] = uu;
}
continue i;
}
}
}
while (true) {
int r = allRoadsPtr++;
int uu = dsuGet(dsu, u[r]), vv = dsuGet(dsu, v[r]);
if (uu != vv) {
out.println(r + 1);
dsuMerge(dsu, uu, vv);
a[uu] += a[vv];
if (roads[uu].size < roads[vv].size) {
IntList tt = roads[uu];
roads[uu] = roads[vv];
roads[vv] = tt;
}
for (int j = 0; j < roads[vv].size; j++) {
roads[uu].push(roads[vv].data[j]);
}
if (a[uu] >= x) {
stack[stackSize++] = uu;
}
continue i;
}
}
}
}

static int scanInt() throws IOException {
return parseInt(scanString());
}

static long scanLong() throws IOException {
return parseLong(scanString());
}

static String scanString() throws IOException {
while (tok == null || !tok.hasMoreTokens()) {
tok = new StringTokenizer(in.readLine());
}
return tok.nextToken();
}

static BufferedReader in;
static PrintWriter out;
static StringTokenizer tok;

public static void main(String[] args) {
try {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
solve();
in.close();
out.close();
} catch (Throwable e) {
e.printStackTrace();
exit(1);
}
}
}

kotlin

import java.io.BufferedReader
import java.io.PrintWriter
import java.util.*
import kotlin.collections.ArrayList

fun main() = tm {
val (nc, nr) = readIntArray(2)
val neededForRoad = readLong()
val aspAtC = readLongArray(nc)
if (aspAtC.sum() < neededForRoad * (nc - 1)) {
println("NO")
[email protected]
}
val connQ = ArrayDeque<Triple<Int, Int, Int>>()
val conns = Array(nc) { LinkedList<Triple<Int, Int, Int>>() }
repeat(nr) {
var (a, b) = readIntArray(2)
--a; --b
val conn = Triple(it + 1, a, b)
if (aspAtC[a] + aspAtC[b] >= neededForRoad) {
connQ += conn
} else {
conns[a].add(conn)
conns[b].add(conn)
}
}
val uf = OneDUF(nc, aspAtC, conns)
val used = HashSet<Int>()
val order = ArrayList<Int>(nc - 1)
while (uf.size(0) != nc && connQ.isNotEmpty()) {
val cnn = connQ.poll()
val (id, a, b) = cnn
val ap = uf.parent(a)
val bp = uf.parent(b)
if (id in used || ap == bp) {
continue
} else if (uf.amount(ap) + uf.amount(bp) < neededForRoad) {
uf.conns(ap).add(cnn)
uf.conns(bp).add(cnn)
continue
}
used += id
order += id
val c = uf.join(ap, bp)
uf.remove(c, neededForRoad)
val aspIn = uf.amount(c)
if (aspIn >= neededForRoad) {
val acs = uf.conns(c)
connQ.addAll(acs)
acs.clear()
} else if (aspIn != 0L) {
val acs = uf.conns(c).iterator()
while (acs.hasNext()) {
val tc = acs.next()
val (_, a2, b2) = tc
if (uf.amount(a2) + uf.amount(b2) >= neededForRoad) {
acs.remove()
connQ += tc
}
}
}
}
if (uf.size(0) == nc) {
println("YES")
println(order.joinToString("\n"))
} else {
println("NO")
}
}

private class OneDUF(sz: Int, val data: LongArray, val conns: Array<LinkedList<Triple<Int, Int, Int>>>) {
val repArray = IntArray(sz) { it }
val szArray = IntArray(sz) { 1 }

tailrec fun parent(pos: Int): Int {
return if (pos == repArray[pos]) pos else parent(repArray[pos])
}

fun join(large: Int, small: Int): Int {
val largep = parent(large)
val smallp = parent(small)
if (largep != smallp) {
return if (szArray[smallp] > szArray[largep]) {
szArray[smallp] += szArray[largep]
data[smallp] += data[largep]
conns[smallp].addAll(conns[largep])
repArray[largep] = smallp
smallp
} else {
szArray[largep] += szArray[smallp]
data[largep] += data[smallp]
conns[largep].addAll(conns[smallp])
repArray[smallp] = largep
largep
}
}
return large
}

fun size(at: Int): Int {
return szArray[parent(at)]
}

fun amount(at: Int): Long {
return data[parent(at)]
}

fun remove(at: Int, amt: Long) {
data[parent(at)] -= amt
}

fun conns(at: Int): LinkedList<Triple<Int, Int, Int>> {
return conns[parent(at)]
}

fun addConn(conn: Triple<Int, Int, Int>) {
conns[parent(conn.second)].add(conn)
conns[parent(conn.third)].add(conn)
}
}

/**
* Template by Nicholas 'sylvyrfysh' Johnson
* <[email protected]>
*/
private inline fun <T> tm(block: FIO.() -> T) {
itm(block)
}

private lateinit var Fio: FIO
private var refs = 0
private inline fun <T> itm(block: FIO.() -> T): T {
if (refs++ == 0) {
Locale.setDefault(Locale.US)
Fio = FIO()
}
val ret = block(Fio)
if (--refs == 0) {
Fio.close()
}
return ret
}

private class FIO(private val r: BufferedReader = System.`in`.bufferedReader()) :
PrintWriter(System.out.bufferedWriter(), false) {
private var tk = StringTokenizer("")

fun readWord(): String {
while (!tk.hasMoreTokens()) {
tk = StringTokenizer(r.readLine() ?: return "", " ")
}
return tk.nextToken()
}

fun clearLine() { tk = StringTokenizer("") }
fun readLine() = r.readLine()
fun readInt() = readWord().toInt()
fun readDouble() = readWord().toDouble()
fun readLong() = readWord().toLong()

fun readIntArray(n: Int = readInt()) = IntArray(n) { readInt() }
fun readLongArray(n: Int = readInt()) = LongArray(n) { readLong() }
fun readDoubleArray(n: Int = readInt()) = DoubleArray(n) { readDouble() }

fun readIntPair() = readInt() to readInt()
fun readLongPair() = readLong() to readLong()

fun dbgln(x: Any) = System.err.println(x)
fun dbgf(x: String, vararg y: Any?) = System.err.printf(x, *y)
}

RUST

//---------- begin union_find ----------
pub struct DSU {
p: Vec<i32>,
}
impl DSU {
pub fn new(n: usize) -> DSU {
assert!(n < std::i32::MAX as usize);
DSU { p: vec![-1; n] }
}
pub fn init(&mut self) {
self.p.iter_mut().for_each(|p| *p = -1);
}
pub fn root(&self, mut x: usize) -> usize {
assert!(x < self.p.len());
while self.p[x] >= 0 {
x = self.p[x] as usize;
}
x
}
pub fn same(&self, x: usize, y: usize) -> bool {
assert!(x < self.p.len() && y < self.p.len());
self.root(x) == self.root(y)
}
pub fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {
assert!(x < self.p.len() && y < self.p.len());
let mut x = self.root(x);
let mut y = self.root(y);
if x == y {
return None;
}
if self.p[x] > self.p[y] {
std::mem::swap(&mut x, &mut y);
}
self.p[x] += self.p[y];
self.p[y] = x as i32;
Some((x, y))
}
pub fn parent(&self, x: usize) -> Option<usize> {
assert!(x < self.p.len());
let p = self.p[x];
if p >= 0 {
Some(p as usize)
} else {
None
}
}
pub fn sum<F>(&self, mut x: usize, mut f: F) -> usize
where
F: FnMut(usize),
{
while let Some(p) = self.parent(x) {
f(x);
x = p;
}
x
}
pub fn size(&self, x: usize) -> usize {
assert!(x < self.p.len());
let r = self.root(x);
(-self.p[r]) as usize
}
}
//---------- end union_find ----------
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}

macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}

macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, bytes) => {
read_value!($iter, String).bytes().collect::<Vec<u8>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
// ---------- end input macro ----------

use std::io::Write;

// 木を与えられた時に解けるか
// 辺の順番
// 切った時に sum a >= (dsu.size(u) - 1) * d && sum a >= (dsu.size(v) - 1) * d
// でないといけない
// a -= d して連結成分の和が-d 未満にならないようにする方法
// a >= -d なので 0以上の物は貪欲に採用していい
// 全部0未満になったら適当でいい
//
// これをうまいこと計算できません
//

fn run() {
input! {
n: usize,
m: usize,
d: i64,
a: [i64; n],
e: [(usize1, usize1); m],
}
let mut a = a;
a.iter_mut().for_each(|a| *a -= d);
if a.iter().sum::<i64>() < -d {
println!("NO");
return;
}
let mut dsu = DSU::new(n);
let mut g = vec![vec![]; n];
for (i, &(a, b)) in e.iter().enumerate() {
if dsu.unite(a, b).is_some() {
g[a].push((a, b, i));
g[b].push((b, a, i));
}
}
dsu.init();
let mut dp = a.clone();
let mut h = std::collections::BinaryHeap::new();
for i in 0..n {
h.push((dp[i], i));
}
let ban = std::i64::MIN / 10;
let mut ans = vec![];
while let Some((x, r)) = h.pop() {
if r != dsu.root(r) || x != dp[r] {
continue;
}
if dsu.size(r) == n || dp[r] <= 0 {
break;
}
let mut p = std::mem::take(&mut g[dsu.root(r)]);
while let Some((a, b, k)) = p.pop() {
if dsu.same(a, b) {
continue;
}
let (a, b) = dsu.unite(a, b).unwrap();
assert!(dp[a] + dp[b] >= -d);
dp[a] += dp[b];
dp[b] = ban;
ans.push(k + 1);
for &b in [a, b].iter() {
if p.len() < g[b].len() {
std::mem::swap(&mut p, &mut g[b]);
}
for q in g[b].drain(..) {
p.push(q);
}
}
break;
}
let r = dsu.root(r);
g[r] = p;
h.push((dp[r], r));
}
for (i, &(a, b)) in e.iter().enumerate() {
if dsu.unite(a, b).is_some() {
ans.push(i + 1);
}
}
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
writeln!(out, "YES").ok();
for k in ans {
writeln!(out, "{}", k).ok();
}
}

fn main() {
run();
}
Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces

PyPy 3 

#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
from collections import deque

class UnionFind:
def __init__(self, n):
self.parent = list(range(n))

def find(self, a):
acopy = a
while a != self.parent[a]:
a = self.parent[a]
while acopy != a:
self.parent[acopy], acopy = a, self.parent[acopy]
return a

def union(self, a, b):
self.parent[self.find(b)] = self.find(a)

def main():
n,m,x = map(int,input().split())
a = list(map(int,input().split()))
edges = {}
adj = []
for _ in range(n):
adj.append([])
for i in range(m):
p,q = map(int,input().split())
adj[p - 1].append(q - 1)
adj[q - 1].append(p - 1)
edges[(p - 1, q - 1)] = i
edges[(q - 1, p - 1)] = i
if sum(a) < x * (n - 1):
print("NO")
else:
parent = [-1] * n
parent[0] = -2
sonCnt = [0] * n
queue = [0]
queueIndex = 0
while len(queue) > queueIndex:
cur = queue[queueIndex]
queueIndex += 1
for elem in adj[cur]:
if parent[elem] == -1:
parent[elem] = cur
queue.append(elem)
sonCnt[cur] += 1
leaf = []
for i in range(n):
if sonCnt[i] == 0:
leaf.append(i)
ans1 = []
ans2 = []
while leaf:
cur = leaf.pop()
if cur == 0:
break
if a[cur] + a[parent[cur]] >= x:
a[parent[cur]] += a[cur]
a[parent[cur]] -= x
ans1.append(edges[(parent[cur], cur)])
else:
ans2.append(edges[(parent[cur], cur)])
sonCnt[parent[cur]] -= 1
if sonCnt[parent[cur]] == 0:
leaf.append(parent[cur])
print("YES")
for elem in ans1:
print(elem + 1)
ans2.reverse()
for elem in ans2:
print(elem + 1)

# ans = []
# uf = UnionFind(n)
# isCovered = [False] * n
# aInd = []
# for i in range(n):
# aInd.append((a[i], i))
# aInd.sort(key = lambda x: x[0], reverse = True)
# for elem in aInd:
# stack = [(-1,elem[1])]
# while stack:
# cur = stack.pop()
# if cur[0] != -1 and (a[uf.find(cur[0])] + a[uf.find(cur[1])] < x or uf.find(cur[0]) == uf.find(cur[1])):
# continue
# if cur[0] != -1:
# a[uf.find(cur[0])] += a[uf.find(cur[1])]
# a[uf.find(cur[0])] -= x
# uf.union(cur[0], cur[1])
# isCovered[cur[0]] = True
# ans.append(edges[(cur[0], cur[1])])
# for elem in adj[cur[1]]:
# if uf.find(elem) != uf.find(cur[1]):
# stack.append((cur[1], elem))
# isCovered[cur[1]] = True
# if len(ans) == n - 1:
# print("YES")
# for elem in ans:
# print(elem + 1)
# else:
# print("NO")





# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
newlines = 0

def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None

def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()

def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()

def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
main()

PYTHON 3

Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces

#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
from collections import deque

class UnionFind:
def __init__(self, n):
self.parent = list(range(n))

def find(self, a):
acopy = a
while a != self.parent[a]:
a = self.parent[a]
while acopy != a:
self.parent[acopy], acopy = a, self.parent[acopy]
return a

def union(self, a, b):
self.parent[self.find(b)] = self.find(a)

def main():
n,m,x = map(int,input().split())
a = list(map(int,input().split()))
edges = {}
adj = []
for _ in range(n):
adj.append([])
for i in range(m):
p,q = map(int,input().split())
adj[p - 1].append(q - 1)
adj[q - 1].append(p - 1)
edges[(p - 1, q - 1)] = i
edges[(q - 1, p - 1)] = i
if sum(a) < x * (n - 1):
print("NO")
else:
parent = [-1] * n
parent[0] = -2
sonCnt = [0] * n
queue = [0]
queueIndex = 0
while len(queue) > queueIndex:
cur = queue[queueIndex]
queueIndex += 1
for elem in adj[cur]:
if parent[elem] == -1:
parent[elem] = cur
queue.append(elem)
sonCnt[cur] += 1
leaf = []
for i in range(n):
if sonCnt[i] == 0:
leaf.append(i)
ans1 = []
ans2 = []
while leaf:
cur = leaf.pop()
if cur == 0:
break
if a[cur] + a[parent[cur]] >= x:
a[parent[cur]] += a[cur]
a[parent[cur]] -= x
ans1.append(edges[(parent[cur], cur)])
else:
ans2.append(edges[(parent[cur], cur)])
sonCnt[parent[cur]] -= 1
if sonCnt[parent[cur]] == 0:
leaf.append(parent[cur])
print("YES")
for elem in ans1:
print(elem + 1)
ans2.reverse()
for elem in ans2:
print(elem + 1)

# ans = []
# uf = UnionFind(n)
# isCovered = [False] * n
# aInd = []
# for i in range(n):
# aInd.append((a[i], i))
# aInd.sort(key = lambda x: x[0], reverse = True)
# for elem in aInd:
# stack = [(-1,elem[1])]
# while stack:
# cur = stack.pop()
# if cur[0] != -1 and (a[uf.find(cur[0])] + a[uf.find(cur[1])] < x or uf.find(cur[0]) == uf.find(cur[1])):
# continue
# if cur[0] != -1:
# a[uf.find(cur[0])] += a[uf.find(cur[1])]
# a[uf.find(cur[0])] -= x
# uf.union(cur[0], cur[1])
# isCovered[cur[0]] = True
# ans.append(edges[(cur[0], cur[1])])
# for elem in adj[cur[1]]:
# if uf.find(elem) != uf.find(cur[1]):
# stack.append((cur[1], elem))
# isCovered[cur[1]] = True
# if len(ans) == n - 1:
# print("YES")
# for elem in ans:
# print(elem + 1)
# else:
# print("NO")





# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
newlines = 0

def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None

def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()

def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()

def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
main()
  Phoenix and Earthquake solution codeforces Splitting a String Into Descending Consecutive Values Minimum Adjacent Swaps to Reach the Kth Smallest Number Minimum Interval to Include Each Query
Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces
 
Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforcesPhoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces Phoenix and Earthquake solution codeforces

Leave a Comment