Submission #88716

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
88716	2018-12-07T18:35:28 Z	popovicirobert	Pipes (BOI13_pipes)	C++14	74.0741 / 100	283 ms	32488 KB

pipes

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MAXM = (int) 5e5;
const int MAXN = (int) 1e5;

vector < pair <int, int> > g[MAXN + 1];
int even[MAXN + 1], father[MAXN + 1], n;
bool vis[MAXN + 1];

void dfs(int nod) {
    vis[nod] = 1;
    for(auto it : g[nod]) {
        if(vis[it.first] == 0) {
            even[it.first] = (even[nod] ^ 1);
            father[it.first] = nod;
            dfs(it.first);
        }
    }
}

inline void detect_cycle(bool &cycle) {
    memset(even, -1, sizeof(even));
    even[1] = 0;
    dfs(1);
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        for(auto it : g[i]) {
            if(even[i] != even[it.first] && !(father[it.first] == i || father[i] == it.first)) {
                cout << 0;
                exit(0);
            }
            if(even[i] == even[it.first]) {
                cnt++;
            }
        }
    }
    cnt /= 2;
    if(cnt > 1) {
        cout << 0;
        exit(0);
    }
    if(cnt) {
        cycle = 1;
    }
}

ll c[MAXN + 1];
ll sol[MAXM + 1];

int deg[MAXN + 1];

inline void solve_tree(bool cycle) {
    int i;
    memset(father, 0, sizeof(father));
    queue <int> Q;
    for(i = 1; i <= n; i++) {
        if(g[i].size() == 1) {
            Q.push(i);
        }
    }
    int root;
    while(Q.size()) {
        int nod = Q.front();
        root = nod;
        Q.pop();
        for(auto it : g[nod]) {
            if(father[it.first] != nod) {
                deg[it.first]++;
                father[nod] = it.first;
                sol[it.second] = c[nod];
                c[it.first] -= c[nod];
                c[nod] = 0;
                if(deg[it.first] + 1 == g[it.first].size()) {
                    Q.push(it.first);
                }
            }
        }
    }
    if(cycle == 0) {
        for(i = 1; i <= n; i++) {
            if(c[i] != 0) {
                cout << 0;
                exit(0);
            }
        }
    }
}

void dfs1(int nod, vector < pair <int, int> > &nodes, int par, int root) {
    vis[nod] = 1;
    for(auto it : g[nod]) {
        if(it.first == par) {
            continue;
        }
        if(vis[it.first] == 0) {
            nodes.push_back({nod, it.second});
            dfs1(it.first, nodes, nod, root);
        }
        else if(it.first == root) {
            nodes.push_back({nod, it.second});
        }
    }
}

inline void solve_cycle(bool cycle) {
    if(cycle == 0) {
        return ;
    }
    int i, nod;
    for(i = 1; i <= n; i++) {
        if(vis[i] == 0) {
            nod = i;
            break;
        }
    }
    vector < pair <int, int> > nodes;
    dfs1(nod, nodes, 0, nod);
    int sz = nodes.size();
    ll tot = 0;
    for(auto it : nodes) {
        tot += c[it.first];
    }
    tot /= 2;
    ll sum = 0;
    for(i = 0; i + 1 < sz; i += 2) {
        sum += c[nodes[i].first];
    }
    sol[nodes[sz - 2].second] = tot - sum;
    c[nodes[sz - 2].first] -= tot - sum;
    for(i = sz - 3; i >= 0; i--) {
        sol[nodes[i].second] = c[nodes[i + 1].first];
        c[nodes[i].first] -= sol[nodes[i].second];
    }
    sum = 0;
    for(auto it : nodes) {
        sum += sol[it.second];
    }
    sol[nodes.back().second] = tot - sum;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(i = 1; i <= n; i++) {
        cin >> c[i];
        c[i] *= 2LL;
    }
    for(i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }
    bool cycle = 0;
    detect_cycle(cycle);
    solve_tree(cycle);
    solve_cycle(cycle);
    for(i = 1; i <= m; i++) {
        cout << sol[i] << "\n";
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

pipes.cpp: In function 'void solve_tree(bool)':
pipes.cpp:80:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(deg[it.first] + 1 == g[it.first].size()) {
                    ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
pipes.cpp:68:9: warning: variable 'root' set but not used [-Wunused-but-set-variable]
     int root;
         ^~~~
pipes.cpp: In function 'void solve_cycle(bool)':
pipes.cpp:124:9: warning: 'nod' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs1(nod, nodes, 0, nod);
     ~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3448 KB	Output is correct
2	Correct	4 ms	3584 KB	Output is correct
3	Correct	5 ms	3616 KB	Output is correct
4	Correct	95 ms	9864 KB	Output is correct
5	Correct	5 ms	9864 KB	Output is correct
6	Correct	4 ms	9864 KB	Output is correct
7	Correct	4 ms	9864 KB	Output is correct
8	Correct	4 ms	9864 KB	Output is correct
9	Correct	5 ms	9864 KB	Output is correct
10	Correct	5 ms	9864 KB	Output is correct
11	Correct	5 ms	9864 KB	Output is correct
12	Correct	5 ms	9864 KB	Output is correct
13	Correct	77 ms	9864 KB	Output is correct
14	Correct	84 ms	9864 KB	Output is correct
15	Correct	93 ms	10152 KB	Output is correct
16	Correct	76 ms	10152 KB	Output is correct
17	Correct	96 ms	10152 KB	Output is correct
18	Correct	88 ms	10152 KB	Output is correct
19	Correct	97 ms	11804 KB	Output is correct
20	Correct	4 ms	11804 KB	Output is correct
21	Correct	5 ms	11804 KB	Output is correct
22	Correct	90 ms	11804 KB	Output is correct
23	Correct	71 ms	11804 KB	Output is correct
24	Correct	95 ms	11804 KB	Output is correct
25	Correct	69 ms	11804 KB	Output is correct

Subtask #2

44.0740740741 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	8 ms	11804 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	10 ms	11804 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Correct	71 ms	13444 KB	Output is correct
4	Correct	88 ms	15020 KB	Output is correct
5	Correct	73 ms	15020 KB	Output is correct
6	Correct	283 ms	25952 KB	Output is correct
7	Runtime error	9 ms	25952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	9 ms	25952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Correct	4 ms	25952 KB	Output is correct
10	Correct	4 ms	25952 KB	Output is correct
11	Correct	4 ms	25952 KB	Output is correct
12	Correct	4 ms	25952 KB	Output is correct
13	Correct	5 ms	25952 KB	Output is correct
14	Runtime error	9 ms	25952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	10 ms	25952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	9 ms	25952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Correct	4 ms	25952 KB	Output is correct
18	Correct	5 ms	25952 KB	Output is correct
19	Correct	5 ms	25952 KB	Output is correct
20	Correct	4 ms	25952 KB	Output is correct
21	Correct	5 ms	25952 KB	Output is correct
22	Runtime error	10 ms	25952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	80 ms	25952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	98 ms	25952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Correct	71 ms	25952 KB	Output is correct
26	Correct	77 ms	25952 KB	Output is correct
27	Correct	73 ms	25952 KB	Output is correct
28	Correct	77 ms	25952 KB	Output is correct
29	Correct	221 ms	31156 KB	Output is correct
30	Runtime error	102 ms	31156 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Runtime error	101 ms	31156 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Runtime error	90 ms	31156 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
33	Correct	75 ms	31156 KB	Output is correct
34	Correct	83 ms	31156 KB	Output is correct
35	Correct	83 ms	31156 KB	Output is correct
36	Correct	74 ms	31156 KB	Output is correct
37	Correct	279 ms	32488 KB	Output is correct
38	Runtime error	99 ms	32488 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	96 ms	32488 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Runtime error	87 ms	32488 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Correct	77 ms	32488 KB	Output is correct
42	Correct	78 ms	32488 KB	Output is correct
43	Correct	84 ms	32488 KB	Output is correct
44	Correct	79 ms	32488 KB	Output is correct
45	Correct	212 ms	32488 KB	Output is correct
46	Runtime error	99 ms	32488 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
47	Runtime error	98 ms	32488 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	101 ms	32488 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Correct	70 ms	32488 KB	Output is correct
50	Correct	80 ms	32488 KB	Output is correct
51	Correct	76 ms	32488 KB	Output is correct
52	Correct	73 ms	32488 KB	Output is correct
53	Correct	210 ms	32488 KB	Output is correct
54	Runtime error	92 ms	32488 KB	Execution killed with signal 11 (could be triggered by violating memory limits)