Submission #84491

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
84491	2018-11-15T15:35:49 Z	Flying_dragon_02	Pipes (BOI13_pipes)	C++14	67.5926 / 100	1000 ms	76032 KB

pipes

#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	2932 KB	Output is correct
3	Correct	6 ms	3136 KB	Output is correct
4	Correct	258 ms	21972 KB	Output is correct
5	Correct	5 ms	21972 KB	Output is correct
6	Correct	4 ms	21972 KB	Output is correct
7	Correct	4 ms	21972 KB	Output is correct
8	Correct	4 ms	21972 KB	Output is correct
9	Correct	5 ms	21972 KB	Output is correct
10	Correct	5 ms	21972 KB	Output is correct
11	Correct	5 ms	21972 KB	Output is correct
12	Correct	5 ms	21972 KB	Output is correct
13	Correct	204 ms	21972 KB	Output is correct
14	Correct	230 ms	21972 KB	Output is correct
15	Correct	249 ms	22160 KB	Output is correct
16	Correct	230 ms	22160 KB	Output is correct
17	Correct	266 ms	22160 KB	Output is correct
18	Correct	240 ms	22176 KB	Output is correct
19	Correct	240 ms	24608 KB	Output is correct
20	Correct	4 ms	24608 KB	Output is correct
21	Correct	5 ms	24608 KB	Output is correct
22	Correct	243 ms	24608 KB	Output is correct
23	Correct	184 ms	24608 KB	Output is correct
24	Correct	248 ms	24608 KB	Output is correct
25	Correct	209 ms	24608 KB	Output is correct

Subtask #2

37.5925925926 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	24608 KB	Output isn't correct
2	Incorrect	5 ms	24608 KB	Output isn't correct
3	Correct	224 ms	24608 KB	Output is correct
4	Correct	214 ms	24608 KB	Output is correct
5	Correct	203 ms	24608 KB	Output is correct
6	Execution timed out	1068 ms	76032 KB	Time limit exceeded
7	Incorrect	5 ms	76032 KB	Output isn't correct
8	Incorrect	5 ms	76032 KB	Output isn't correct
9	Correct	4 ms	76032 KB	Output is correct
10	Correct	4 ms	76032 KB	Output is correct
11	Correct	4 ms	76032 KB	Output is correct
12	Correct	4 ms	76032 KB	Output is correct
13	Correct	4 ms	76032 KB	Output is correct
14	Incorrect	5 ms	76032 KB	Output isn't correct
15	Incorrect	5 ms	76032 KB	Output isn't correct
16	Incorrect	5 ms	76032 KB	Output isn't correct
17	Correct	5 ms	76032 KB	Output is correct
18	Correct	5 ms	76032 KB	Output is correct
19	Correct	5 ms	76032 KB	Output is correct
20	Correct	5 ms	76032 KB	Output is correct
21	Correct	6 ms	76032 KB	Output is correct
22	Incorrect	5 ms	76032 KB	Output isn't correct
23	Incorrect	264 ms	76032 KB	Output isn't correct
24	Incorrect	307 ms	76032 KB	Output isn't correct
25	Correct	236 ms	76032 KB	Output is correct
26	Correct	225 ms	76032 KB	Output is correct
27	Correct	220 ms	76032 KB	Output is correct
28	Correct	227 ms	76032 KB	Output is correct
29	Execution timed out	1035 ms	76032 KB	Time limit exceeded
30	Incorrect	306 ms	76032 KB	Output isn't correct
31	Incorrect	372 ms	76032 KB	Output isn't correct
32	Incorrect	241 ms	76032 KB	Output isn't correct
33	Correct	209 ms	76032 KB	Output is correct
34	Correct	200 ms	76032 KB	Output is correct
35	Correct	198 ms	76032 KB	Output is correct
36	Correct	207 ms	76032 KB	Output is correct
37	Execution timed out	1069 ms	76032 KB	Time limit exceeded
38	Incorrect	309 ms	76032 KB	Output isn't correct
39	Incorrect	247 ms	76032 KB	Output isn't correct
40	Incorrect	289 ms	76032 KB	Output isn't correct
41	Correct	256 ms	76032 KB	Output is correct
42	Correct	193 ms	76032 KB	Output is correct
43	Correct	191 ms	76032 KB	Output is correct
44	Correct	181 ms	76032 KB	Output is correct
45	Execution timed out	1086 ms	76032 KB	Time limit exceeded
46	Incorrect	296 ms	76032 KB	Output isn't correct
47	Incorrect	295 ms	76032 KB	Output isn't correct
48	Incorrect	305 ms	76032 KB	Output isn't correct
49	Correct	233 ms	76032 KB	Output is correct
50	Correct	206 ms	76032 KB	Output is correct
51	Correct	200 ms	76032 KB	Output is correct
52	Correct	173 ms	76032 KB	Output is correct
53	Execution timed out	1089 ms	76032 KB	Time limit exceeded
54	Incorrect	280 ms	76032 KB	Output isn't correct