Submission #88715

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
88715	2018-12-07T18:34:02 Z	popovicirobert	Pipes (BOI13_pipes)	C++14	74.0741 / 100	297 ms	32500 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 && c[root] != 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:86:28: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(cycle == 0 && c[root] != 0) {
                      ~~~~~~^
pipes.cpp: In function 'void solve_cycle(bool)':
pipes.cpp:120: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	4 ms	3576 KB	Output is correct
2	Correct	4 ms	3576 KB	Output is correct
3	Correct	5 ms	3592 KB	Output is correct
4	Correct	83 ms	9800 KB	Output is correct
5	Correct	4 ms	9800 KB	Output is correct
6	Correct	4 ms	9800 KB	Output is correct
7	Correct	5 ms	9800 KB	Output is correct
8	Correct	4 ms	9800 KB	Output is correct
9	Correct	5 ms	9800 KB	Output is correct
10	Correct	5 ms	9800 KB	Output is correct
11	Correct	5 ms	9800 KB	Output is correct
12	Correct	5 ms	9800 KB	Output is correct
13	Correct	72 ms	9800 KB	Output is correct
14	Correct	89 ms	9800 KB	Output is correct
15	Correct	93 ms	10108 KB	Output is correct
16	Correct	73 ms	10108 KB	Output is correct
17	Correct	84 ms	10108 KB	Output is correct
18	Correct	94 ms	10108 KB	Output is correct
19	Correct	99 ms	11720 KB	Output is correct
20	Correct	5 ms	11720 KB	Output is correct
21	Correct	5 ms	11720 KB	Output is correct
22	Correct	89 ms	11720 KB	Output is correct
23	Correct	79 ms	11720 KB	Output is correct
24	Correct	97 ms	11720 KB	Output is correct
25	Correct	67 ms	11720 KB	Output is correct

Subtask #2
44.0740740741 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	9 ms	11720 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	10 ms	11720 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Correct	73 ms	13396 KB	Output is correct
4	Correct	158 ms	14912 KB	Output is correct
5	Correct	74 ms	14912 KB	Output is correct
6	Correct	267 ms	25896 KB	Output is correct
7	Runtime error	9 ms	25896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	11 ms	25896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Correct	4 ms	25896 KB	Output is correct
10	Correct	4 ms	25896 KB	Output is correct
11	Correct	4 ms	25896 KB	Output is correct
12	Correct	4 ms	25896 KB	Output is correct
13	Correct	4 ms	25896 KB	Output is correct
14	Runtime error	9 ms	25896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	10 ms	25896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	9 ms	25896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Correct	5 ms	25896 KB	Output is correct
18	Correct	4 ms	25896 KB	Output is correct
19	Correct	4 ms	25896 KB	Output is correct
20	Correct	5 ms	25896 KB	Output is correct
21	Correct	5 ms	25896 KB	Output is correct
22	Runtime error	9 ms	25896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	76 ms	25896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	96 ms	25896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Correct	71 ms	25896 KB	Output is correct
26	Correct	80 ms	25896 KB	Output is correct
27	Correct	82 ms	25896 KB	Output is correct
28	Correct	96 ms	25896 KB	Output is correct
29	Correct	250 ms	31020 KB	Output is correct
30	Runtime error	107 ms	31020 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Runtime error	104 ms	31020 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Runtime error	91 ms	31020 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
33	Correct	79 ms	31020 KB	Output is correct
34	Correct	86 ms	31020 KB	Output is correct
35	Correct	83 ms	31020 KB	Output is correct
36	Correct	75 ms	31020 KB	Output is correct
37	Correct	297 ms	32500 KB	Output is correct
38	Runtime error	99 ms	32500 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	93 ms	32500 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Runtime error	108 ms	32500 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Correct	91 ms	32500 KB	Output is correct
42	Correct	82 ms	32500 KB	Output is correct
43	Correct	83 ms	32500 KB	Output is correct
44	Correct	71 ms	32500 KB	Output is correct
45	Correct	223 ms	32500 KB	Output is correct
46	Runtime error	104 ms	32500 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
47	Runtime error	90 ms	32500 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	97 ms	32500 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Correct	63 ms	32500 KB	Output is correct
50	Correct	77 ms	32500 KB	Output is correct
51	Correct	75 ms	32500 KB	Output is correct
52	Correct	69 ms	32500 KB	Output is correct
53	Correct	209 ms	32500 KB	Output is correct
54	Runtime error	104 ms	32500 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Submission #88715

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 44.0740740741 / 70.0

Subtask #1
30.0 / 30.0

Subtask #2
44.0740740741 / 70.0