oj.uz

Submission #1111252

# Submission time Handle Problem Language Result Execution time Memory
1111252 2024-11-11T20:47:32 Z codexistent Pipes (BOI13_pipes) C++14
74.0741 / 100
 289 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100005
#define MAXM 500005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define f first
#define s second

ll n, m, t[MAXN], en[MAXN], r[MAXM];
pair<ll, ll> e[MAXM];
vector<pair<ll, ll>> adj[MAXN];
bool v[MAXN];

int main(){
    cin >> n >> m;
    FOR(i, 1, n) {
        cin >> t[i];
        en[i] = 0, v[i] = false;
    }
    FOR(i, 1, m){
        cin >> e[i].f >> e[i].s;
        adj[e[i].f].push_back({e[i].s, i}), en[e[i].f]++;
        adj[e[i].s].push_back({e[i].f, i}), en[e[i].s]++;
        r[i] = 1000000001;
    }
    if(!(m == n - 1 || m == n)) return cout << 0 << endl, 0;

    queue<ll> q;
    FOR(i, 1, n) if(en[i] == 1) q.push(i);

    ll d = n;
    while(q.size()){
        ll qi = q.front(); q.pop();
        if(v[qi]) continue;
        v[qi] = true, d--;
        if(en[qi] == 0) continue;

        for(pair<ll, ll> p : adj[qi]) if(r[p.s] == 1000000001) {
            r[p.s] = 2 * t[qi];
            t[p.f] -= t[qi], en[p.f]--;

            if(!v[p.f] && en[p.f] == 1) q.push(p.f);
        }
    }

    if(d != 0 && d % 2 == 0) return cout << 0 << endl, 0;

    ll stt, ci = -1;
    FOR(i, 1, n) if(!v[i]) ci = i;
    if(ci == -1) {
        FOR(i, 1, m) cout << r[i] << endl;
        return 0;
    }
    stt = ci;

    stack<ll> st;
    ll alts = 0;
    do{
        for(pair<ll, ll> p : adj[ci]) if(r[p.s] == 1000000001) {
            alts = p.s + (-1)*(alts);
            ci = p.f;
            break;
       }
        st.push(ci);
    }while(stt != ci);

    ll prvi;
    for(pair<ll, ll> p : adj[stt]) if(r[p.s] == 1000000001) {
        prvi = r[p.s] = t[stt] - alts;
        if(prvi % 2) return cout << 0 << endl, 0;
    }

    st.pop();
    while(!st.empty()){
        ll sti = st.top(); st.pop();

        for(pair<ll, ll> p : adj[sti]) if(e[p.s].f == prvi || e[p.s].s == prvi) {
            prvi = r[p.s] = 2 * (r[sti] - prvi / 2);
            if(prvi % 2) return cout << 0 << endl, 0;
        }
    }

    FOR(i, 1, m) cout << r[i] << endl;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:78:60: warning: 'prvi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         for(pair<ll, ll> p : adj[sti]) if(e[p.s].f == prvi || e[p.s].s == prvi) {
      |                                           ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 4 ms 2924 KB Output is correct
4 Correct 235 ms 12664 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 2 ms 2640 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 4 ms 3064 KB Output is correct
10 Correct 4 ms 2896 KB Output is correct
11 Correct 4 ms 2896 KB Output is correct
12 Correct 4 ms 2896 KB Output is correct
13 Correct 168 ms 10604 KB Output is correct
14 Correct 200 ms 12108 KB Output is correct
15 Correct 217 ms 12620 KB Output is correct
16 Correct 187 ms 11080 KB Output is correct
17 Correct 206 ms 12616 KB Output is correct
18 Correct 201 ms 12616 KB Output is correct
19 Correct 214 ms 12360 KB Output is correct
20 Correct 2 ms 2640 KB Output is correct
21 Correct 4 ms 2896 KB Output is correct
22 Correct 205 ms 12676 KB Output is correct
23 Correct 159 ms 10728 KB Output is correct
24 Correct 216 ms 12576 KB Output is correct
25 Correct 176 ms 11136 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 153 ms 131072 KB Execution killed with signal 9
2 Runtime error 154 ms 131072 KB Execution killed with signal 9
3 Correct 60 ms 11592 KB Output is correct
4 Correct 63 ms 11848 KB Output is correct
5 Correct 62 ms 11860 KB Output is correct
6 Correct 244 ms 42040 KB Output is correct
7 Runtime error 150 ms 131072 KB Execution killed with signal 9
8 Runtime error 174 ms 131072 KB Execution killed with signal 9
9 Correct 3 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 2 ms 2640 KB Output is correct
13 Correct 2 ms 2640 KB Output is correct
14 Runtime error 161 ms 131072 KB Execution killed with signal 9
15 Runtime error 148 ms 131072 KB Execution killed with signal 9
16 Runtime error 164 ms 131072 KB Execution killed with signal 9
17 Correct 3 ms 2896 KB Output is correct
18 Correct 3 ms 2896 KB Output is correct
19 Correct 3 ms 2896 KB Output is correct
20 Correct 3 ms 3064 KB Output is correct
21 Correct 3 ms 2896 KB Output is correct
22 Runtime error 154 ms 131072 KB Execution killed with signal 9
23 Runtime error 199 ms 131072 KB Execution killed with signal 9
24 Runtime error 221 ms 131072 KB Execution killed with signal 9
25 Correct 62 ms 11592 KB Output is correct
26 Correct 60 ms 11856 KB Output is correct
27 Correct 69 ms 11784 KB Output is correct
28 Correct 64 ms 12180 KB Output is correct
29 Correct 209 ms 37192 KB Output is correct
30 Runtime error 197 ms 131072 KB Execution killed with signal 9
31 Runtime error 189 ms 131072 KB Execution killed with signal 9
32 Runtime error 206 ms 131072 KB Execution killed with signal 9
33 Correct 66 ms 11992 KB Output is correct
34 Correct 63 ms 11848 KB Output is correct
35 Correct 75 ms 12944 KB Output is correct
36 Correct 67 ms 11864 KB Output is correct
37 Correct 289 ms 42024 KB Output is correct
38 Runtime error 229 ms 131072 KB Execution killed with signal 9
39 Runtime error 200 ms 131072 KB Execution killed with signal 9
40 Runtime error 202 ms 131072 KB Execution killed with signal 9
41 Correct 64 ms 11848 KB Output is correct
42 Correct 62 ms 11856 KB Output is correct
43 Correct 60 ms 11720 KB Output is correct
44 Correct 59 ms 11588 KB Output is correct
45 Correct 190 ms 37584 KB Output is correct
46 Runtime error 208 ms 131072 KB Execution killed with signal 9
47 Runtime error 205 ms 131072 KB Execution killed with signal 9
48 Runtime error 210 ms 131072 KB Execution killed with signal 9
49 Correct 71 ms 11756 KB Output is correct
50 Correct 65 ms 11848 KB Output is correct
51 Correct 67 ms 11848 KB Output is correct
52 Correct 64 ms 11848 KB Output is correct
53 Correct 237 ms 37188 KB Output is correct
54 Runtime error 204 ms 131072 KB Execution killed with signal 9