답안 #84492 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
84492	2018-11-15T15:36:40 Z	Flying_dragon_02	Pipes (BOI13_pipes)	C++14	72.7778 / 100	1000 ms	80896 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #84492

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 42.7777777778 / 70.0

Subtask #1
30.0 / 30.0

Subtask #2
42.7777777778 / 70.0