oj.uz

Submission #84492

# Submission time Handle Problem Language Result Execution time Memory
84492 2018-11-15T15:36:40 Z Flying_dragon_02 Pipes (BOI13_pipes) C++14
72.7778 / 100
 1000 ms 80896 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 && in[v] == 0) {
            int z = u;
            while(z != v) {
                if(z == 0) break;
                cycle.pb(z);
                in[z] = 1;
                z = par[z].fi;
            }
            in[v] = 1;
            cycle.pb(v);
            continue;
        }
        if(vis[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));
    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++) {
        if(x[i] > 1000000000 || x[i] < -1000000000)
            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:49: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:115:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cycle.size(); i++) {
                    ~~^~~~~~~~~~~~~~
pipes.cpp:126: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 4 ms 2808 KB Output is correct
2 Correct 4 ms 2844 KB Output is correct
3 Correct 5 ms 3140 KB Output is correct
4 Correct 261 ms 21928 KB Output is correct
5 Correct 4 ms 21928 KB Output is correct
6 Correct 4 ms 21928 KB Output is correct
7 Correct 4 ms 21928 KB Output is correct
8 Correct 4 ms 21928 KB Output is correct
9 Correct 5 ms 21928 KB Output is correct
10 Correct 5 ms 21928 KB Output is correct
11 Correct 5 ms 21928 KB Output is correct
12 Correct 6 ms 21928 KB Output is correct
13 Correct 192 ms 21928 KB Output is correct
14 Correct 236 ms 21928 KB Output is correct
15 Correct 270 ms 22288 KB Output is correct
16 Correct 214 ms 22288 KB Output is correct
17 Correct 238 ms 22288 KB Output is correct
18 Correct 253 ms 22288 KB Output is correct
19 Correct 287 ms 24568 KB Output is correct
20 Correct 4 ms 24568 KB Output is correct
21 Correct 5 ms 24568 KB Output is correct
22 Correct 256 ms 24568 KB Output is correct
23 Correct 182 ms 24568 KB Output is correct
24 Correct 268 ms 24568 KB Output is correct
25 Correct 206 ms 24568 KB Output is correct

Subtask #2
42.7777777778 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 24568 KB Output isn't correct
2 Incorrect 5 ms 24568 KB Output isn't correct
3 Correct 252 ms 24568 KB Output is correct
4 Correct 202 ms 24568 KB Output is correct
5 Correct 209 ms 24568 KB Output is correct
6 Execution timed out 1084 ms 77204 KB Time limit exceeded
7 Incorrect 4 ms 77204 KB Output isn't correct
8 Correct 4 ms 77204 KB Output is correct
9 Correct 4 ms 77204 KB Output is correct
10 Correct 4 ms 77204 KB Output is correct
11 Correct 4 ms 77204 KB Output is correct
12 Correct 4 ms 77204 KB Output is correct
13 Correct 4 ms 77204 KB Output is correct
14 Incorrect 4 ms 77204 KB Output isn't correct
15 Incorrect 6 ms 77204 KB Output isn't correct
16 Correct 6 ms 77204 KB Output is correct
17 Correct 5 ms 77204 KB Output is correct
18 Correct 5 ms 77204 KB Output is correct
19 Correct 5 ms 77204 KB Output is correct
20 Correct 5 ms 77204 KB Output is correct
21 Correct 6 ms 77204 KB Output is correct
22 Incorrect 6 ms 77204 KB Output isn't correct
23 Incorrect 232 ms 77204 KB Output isn't correct
24 Incorrect 307 ms 77204 KB Output isn't correct
25 Correct 229 ms 77204 KB Output is correct
26 Correct 209 ms 77204 KB Output is correct
27 Correct 206 ms 77204 KB Output is correct
28 Correct 219 ms 77204 KB Output is correct
29 Execution timed out 1047 ms 77204 KB Time limit exceeded
30 Correct 318 ms 77204 KB Output is correct
31 Incorrect 324 ms 77204 KB Output isn't correct
32 Incorrect 269 ms 77204 KB Output isn't correct
33 Correct 228 ms 77204 KB Output is correct
34 Correct 214 ms 77204 KB Output is correct
35 Correct 214 ms 77204 KB Output is correct
36 Correct 209 ms 77204 KB Output is correct
37 Execution timed out 1081 ms 80896 KB Time limit exceeded
38 Incorrect 313 ms 80896 KB Output isn't correct
39 Incorrect 271 ms 80896 KB Output isn't correct
40 Incorrect 292 ms 80896 KB Output isn't correct
41 Correct 238 ms 80896 KB Output is correct
42 Correct 200 ms 80896 KB Output is correct
43 Correct 204 ms 80896 KB Output is correct
44 Correct 207 ms 80896 KB Output is correct
45 Execution timed out 1088 ms 80896 KB Time limit exceeded
46 Incorrect 329 ms 80896 KB Output isn't correct
47 Incorrect 302 ms 80896 KB Output isn't correct
48 Incorrect 347 ms 80896 KB Output isn't correct
49 Correct 224 ms 80896 KB Output is correct
50 Correct 206 ms 80896 KB Output is correct
51 Correct 202 ms 80896 KB Output is correct
52 Correct 211 ms 80896 KB Output is correct
53 Execution timed out 1080 ms 80896 KB Time limit exceeded
54 Correct 281 ms 80896 KB Output is correct