oj.uz

Submission #59158

# Submission time Handle Problem Language Result Execution time Memory
59158 2018-07-20T21:10:13 Z Benq Pipes (BOI13_pipes) C++14
28.5185 / 100
 372 ms 119664 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N,M,in[MX],c[MX],ans[MX];
bool done[MX];
vpi adj[MX];

template<int SZ> struct DSU {
    int par[SZ], sz[SZ], val[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) {
    	    val[x] ++;
    	    return 0;
    	}
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], val[x] += val[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;

vpi v;

void genCyc(int pre, int cur) {
    done[cur] = 1;
    for (auto a: adj[cur]) if (a.f != pre && !done[a.f]) {
        v.pb(a);
        genCyc(cur,a.f);
    }
}

ll cum[2*MX];

void solveCyc(int x) {
    v.clear(); 
    int pre = -1;
    for (auto y: adj[x]) if (!done[y.f]) {
        v.pb({x,y.s});
        pre = y.f;
        break;
    }
    genCyc(pre,x);
    if (sz(v) % 2 == 0) {
        cout << 0;
        exit(0);
    }
    ll sum = 0;
    for (auto a: v) sum += c[a.f];
    sum /= 2;
    
    F0R(i,2*sz(v)) {
        cum[i] = c[v[2*i%N].f];
        if (i) cum[i] += cum[i-1];
    }
    
    // v[1].s: {v[0].f,v[1].f}
    // v[3].s: {v[2].f,v[3].f}
    // 0: sum-(2+4+6+...+(N-1))
    F0R(i,sz(v)) {
        ans[v[i].s] = sum;
        int x = i+1; if (x&1) x += sz(v);
        // i+1, i+3, ..., i+N-2
        ans[v[i].s] += cum[x/2-1];
        ans[v[i].s] -= cum[(x+sz(v)-3)/2];
        // cout << "AH " << x << " " << sum << " " << cum[x/2-1] << " " << cum[(x+N-3)/2] << " " << ans[v[i].s] << "\n";
    }
    
    // cout << sz(v);
    // for (auto a: v) cout << a.f << " " << a.s << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    FOR(i,1,N+1) cin >> c[i];
    FOR(i,1,M+1) {
        int a,b; cin >> a >> b;
        adj[a].pb({b,i}), adj[b].pb({a,i});
        D.unite(a,b);
        in[a] ++, in[b] ++;
    }
    FOR(i,1,N+1) if (D.val[D.get(i)] > D.sz[D.get(i)]) {
        cout << 0;
        exit(0);
    }
    queue<int> q;
    FOR(i,1,N+1) if (in[i] == 1) q.push(i);
    while (sz(q)) {
        int x = q.front(); q.pop(); done[x] = 1;
        for (auto a: adj[x]) if (!done[a.f]) {
            ans[a.s] = c[x];
            c[a.f] -= ans[a.s];
        }
    }
    FOR(i,1,N+1) if (!done[i]) solveCyc(i);
    FOR(i,1,M+1) cout << 2*ans[i] << "\n";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3576 KB Output isn't correct
2 Incorrect 6 ms 3700 KB Output isn't correct
3 Incorrect 5 ms 3752 KB Output isn't correct
4 Incorrect 126 ms 11440 KB Output isn't correct
5 Incorrect 6 ms 11440 KB Output isn't correct
6 Incorrect 6 ms 11440 KB Output isn't correct
7 Incorrect 7 ms 11440 KB Output isn't correct
8 Incorrect 5 ms 11440 KB Output isn't correct
9 Incorrect 6 ms 11440 KB Output isn't correct
10 Incorrect 6 ms 11440 KB Output isn't correct
11 Runtime error 12 ms 11440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 7 ms 11440 KB Output isn't correct
13 Runtime error 80 ms 19104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 94 ms 21360 KB Output isn't correct
15 Incorrect 122 ms 23784 KB Output isn't correct
16 Runtime error 88 ms 25300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 132 ms 27696 KB Output isn't correct
18 Runtime error 122 ms 30168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 128 ms 36760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 6 ms 36760 KB Output isn't correct
21 Incorrect 7 ms 36760 KB Output isn't correct
22 Incorrect 119 ms 36760 KB Output isn't correct
23 Runtime error 68 ms 36760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 138 ms 36760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Incorrect 90 ms 36760 KB Output isn't correct

Subtask #2
28.5185185185 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 36760 KB Output isn't correct
2 Incorrect 7 ms 36760 KB Output isn't correct
3 Runtime error 137 ms 43872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 145 ms 45404 KB Output is correct
5 Runtime error 113 ms 45404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Correct 372 ms 57100 KB Output is correct
7 Incorrect 4 ms 57100 KB Output isn't correct
8 Incorrect 7 ms 57100 KB Output isn't correct
9 Incorrect 5 ms 57100 KB Output isn't correct
10 Correct 6 ms 57100 KB Output is correct
11 Correct 7 ms 57100 KB Output is correct
12 Correct 5 ms 57100 KB Output is correct
13 Correct 5 ms 57100 KB Output is correct
14 Incorrect 6 ms 57100 KB Output isn't correct
15 Incorrect 6 ms 57100 KB Output isn't correct
16 Incorrect 8 ms 57100 KB Output isn't correct
17 Correct 7 ms 57100 KB Output is correct
18 Correct 5 ms 57100 KB Output is correct
19 Incorrect 7 ms 57100 KB Output isn't correct
20 Correct 6 ms 57100 KB Output is correct
21 Correct 6 ms 57100 KB Output is correct
22 Incorrect 6 ms 57100 KB Output isn't correct
23 Incorrect 90 ms 57100 KB Output isn't correct
24 Incorrect 146 ms 57100 KB Output isn't correct
25 Runtime error 99 ms 57656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Correct 100 ms 61800 KB Output is correct
27 Incorrect 111 ms 64716 KB Output isn't correct
28 Correct 145 ms 64716 KB Output is correct
29 Correct 322 ms 71172 KB Output is correct
30 Incorrect 78 ms 71172 KB Output isn't correct
31 Incorrect 153 ms 75192 KB Output isn't correct
32 Incorrect 148 ms 75192 KB Output isn't correct
33 Incorrect 159 ms 76228 KB Output isn't correct
34 Correct 128 ms 76228 KB Output is correct
35 Correct 129 ms 76916 KB Output is correct
36 Correct 129 ms 76916 KB Output is correct
37 Correct 351 ms 90972 KB Output is correct
38 Incorrect 168 ms 90972 KB Output isn't correct
39 Runtime error 104 ms 90972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Incorrect 140 ms 90972 KB Output isn't correct
41 Incorrect 138 ms 93968 KB Output isn't correct
42 Incorrect 132 ms 95752 KB Output isn't correct
43 Incorrect 149 ms 95752 KB Output isn't correct
44 Runtime error 117 ms 95752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Correct 342 ms 102832 KB Output is correct
46 Incorrect 129 ms 102832 KB Output isn't correct
47 Incorrect 137 ms 102832 KB Output isn't correct
48 Incorrect 129 ms 105716 KB Output isn't correct
49 Runtime error 142 ms 105716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Correct 132 ms 107548 KB Output is correct
51 Correct 114 ms 108204 KB Output is correct
52 Correct 148 ms 108860 KB Output is correct
53 Correct 301 ms 119664 KB Output is correct
54 Incorrect 116 ms 119664 KB Output isn't correct