oj.uz

Submission #84487

# Submission time Handle Problem Language Result Execution time Memory
84487 2018-11-15T15:08:25 Z Flying_dragon_02 Pipes (BOI13_pipes) C++14
30 / 100
 1000 ms 132096 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 1e5 + 5;

int n, m, c[N], deg[N];
long long x[5 * N];

ii par[N];

vector<ii> graph[N];

bool vis[N], in[N];

vector<int> cycle;

void dfs(int u, int p, int type) {
    vis[u] = 1;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i].fi;
        if(v == p) continue;
        if(vis[v] && type == 0) {
            int z = u;
            while(z != v) {
                cycle.pb(z);
                z = par[z].fi;
            }
            cycle.pb(v);
            continue;
        }
        par[v] = {u, graph[u][i].se};
        dfs(v, u, type);
    }
}

void bfs(int u, int p) {
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i].fi;
        if(v == p) continue;
        bfs(v, u);
    }
    if(u != 1) {
        ii lmao = par[u];
        x[lmao.se] = 2 * c[u];
        c[lmao.fi] = c[lmao.fi] - c[u];
        c[u] = 0;
    }
}

void bye() {
    cout << "0\n";
    exit(0);
}

map<ii, int> edge;

queue<int> q;

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> c[i];
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edge[{u, v}] = i;
        edge[{v, u}] = i;
        ++deg[u]; ++deg[v];
        graph[u].pb({v, i});
        graph[v].pb({u, i});
    }
    if(n < m)
        bye();
    dfs(1, 1, 0);
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < cycle.size(); i++)
        in[cycle[i]] = 1;
    if(n == m + 1) {
        bfs(1, 1);
        if(c[1] != 0)
            bye();
        for(int i = 1; i <= m; i++)
            cout << x[i] << "\n";
        exit(0);
    }
    if(cycle.size() % 2 == 0)
        bye();
    dfs(cycle[0], cycle[0], 1);
    for(int i = 1; i <= n; i++) {
        if(deg[i] == 1)
            q.push(i);
    }
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        ii lmao = par[u];
        x[lmao.se] = 2 * c[u];
        c[lmao.fi] = c[lmao.fi] - c[u];
        c[u] = 0;
        if(in[lmao.fi] == 0)
            q.push(lmao.fi);
    }
    long long total = 0, s = cycle.size() - 1;
    for(int i = 0; i < cycle.size(); i++) {
        if(i % 2 == 0)
            total += c[cycle[i]];
        else
            total -= c[cycle[i]];
    }
    x[edge[{cycle[0], cycle[s]}]] = total;
    if(total % 2 != 0)
        bye();
    c[cycle[0]] -= total / 2;
    c[cycle[s]] -= total / 2;
    for(int i = 0; i < cycle.size() - 1; i++) {
        x[edge[{cycle[i], cycle[i + 1]}]] = 2 * c[cycle[i]];
        c[cycle[i + 1]] = c[cycle[i + 1]] - c[cycle[i]];
        c[cycle[i]] = 0;
    }
    if(c[cycle[s]] != 0)
        bye();
    for(int i = 1; i <= m; i++)
        cout << x[i] << "\n";
}

Compilation message

pipes.cpp: In function 'void dfs(int, int, int)':
pipes.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'void bfs(int, int)':
pipes.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cycle.size(); i++)
                    ~~^~~~~~~~~~~~~~
pipes.cpp:113:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cycle.size(); i++) {
                    ~~^~~~~~~~~~~~~~
pipes.cpp:124:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cycle.size() - 1; i++) {
                    ~~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2948 KB Output is correct
3 Correct 6 ms 3032 KB Output is correct
4 Correct 243 ms 23188 KB Output is correct
5 Correct 4 ms 23188 KB Output is correct
6 Correct 4 ms 23188 KB Output is correct
7 Correct 4 ms 23188 KB Output is correct
8 Correct 5 ms 23188 KB Output is correct
9 Correct 5 ms 23188 KB Output is correct
10 Correct 5 ms 23188 KB Output is correct
11 Correct 5 ms 23188 KB Output is correct
12 Correct 5 ms 23188 KB Output is correct
13 Correct 193 ms 23188 KB Output is correct
14 Correct 247 ms 25180 KB Output is correct
15 Correct 235 ms 27556 KB Output is correct
16 Correct 193 ms 27556 KB Output is correct
17 Correct 223 ms 27636 KB Output is correct
18 Correct 230 ms 28372 KB Output is correct
19 Correct 251 ms 32360 KB Output is correct
20 Correct 4 ms 32360 KB Output is correct
21 Correct 5 ms 32360 KB Output is correct
22 Correct 243 ms 32360 KB Output is correct
23 Correct 180 ms 32360 KB Output is correct
24 Correct 210 ms 32360 KB Output is correct
25 Correct 183 ms 32360 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 257 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 249 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 411 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 175 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
5 Runtime error 214 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
6 Execution timed out 1081 ms 132096 KB Time limit exceeded
7 Runtime error 256 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 254 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 248 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 5 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
11 Runtime error 4 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
12 Runtime error 4 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
13 Runtime error 4 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
14 Runtime error 252 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 254 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 251 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 263 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 5 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
19 Runtime error 5 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
20 Runtime error 5 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
21 Runtime error 6 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
22 Runtime error 246 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 363 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 395 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 398 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 173 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
27 Runtime error 172 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
28 Runtime error 206 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
29 Runtime error 910 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
30 Runtime error 395 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 422 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 433 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 403 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 205 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
35 Runtime error 214 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
36 Runtime error 197 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
37 Execution timed out 1083 ms 132096 KB Time limit exceeded
38 Runtime error 411 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 405 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 408 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 419 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 192 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
43 Runtime error 198 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
44 Runtime error 176 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
45 Execution timed out 1067 ms 132096 KB Time limit exceeded
46 Runtime error 424 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 405 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Runtime error 423 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Runtime error 405 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Runtime error 198 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
51 Runtime error 169 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
52 Runtime error 180 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
53 Execution timed out 1084 ms 132096 KB Time limit exceeded
54 Runtime error 428 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)