답안 #79877 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79877	2018-10-17T03:12:40 Z	win11905	Pipes (BOI13_pipes)	C++11	83.1481 / 100	210 ms	97020 KB

pipes

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;

int n, m, s[N], t[N];
int A[N], deg[N];
int ans[N];

set<int> g[N];

void answer() {
    for(int i = 0; i < m; ++i) printf("%d\n", ans[i]);
    exit(0);
}

queue<int> Q;

void solve() {
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int x : g[u]) {
            int v = u ^ s[x] ^ t[x]; 
            g[v].erase(x);
            A[v] -= A[u];
            ans[x] = A[u] << 1;
            if(g[v].size() == 1) Q.emplace(v);
        }
        g[u].clear();
    }
}

int cnt = 0;

void dfs(int u, int p) {
    static int idx = 0;
    static int sum = 0;
    idx++;
    if(idx & 1) sum += A[u];
    else sum -= A[u];
    int z = -1;
    for(auto i : g[u]) {
        int v = u ^ s[i] ^ t[i];
        if(v != p) {
            if(cnt == idx) {
                ans[i] = sum;
                A[u] -= sum / 2, A[v] -= sum / 2;
                z = i;
                break;
            }
            dfs(v, u);
        }
    }
    if(cnt == idx) {
        int v = u ^ s[z] ^ t[z];
        g[v].erase(z), g[u].erase(z);
        Q.emplace(u);
    } 
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", A+i);
    for(int i = 0; i < m; ++i) {
        scanf("%d %d", s+i, t+i);
        g[s[i]].emplace(i), g[t[i]].emplace(i);
        deg[s[i]]++, deg[t[i]]++;
    }
    if(n < m) return puts("0"), 0;
    for(int i = 1; i <= n; ++i) if(deg[i] == 1) Q.emplace(i);
    solve(); 
    if(n == m+1) answer();
    for(int i = 1; i <= n; ++i) if(g[i].size()) cnt++;
    if(cnt % 2 == 0) return puts("0"), 0;
    for(int i = 1; i <= n; ++i) {
        if(g[i].size()) dfs(i, i);
        break;
    }
    solve();
    answer();
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:63:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%d", A+i);
                                 ~~~~~^~~~~~~~~~~
pipes.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", s+i, t+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5084 KB	Output is correct
2	Correct	6 ms	5120 KB	Output is correct
3	Correct	7 ms	5200 KB	Output is correct
4	Correct	146 ms	18640 KB	Output is correct
5	Correct	6 ms	18640 KB	Output is correct
6	Correct	6 ms	18640 KB	Output is correct
7	Correct	6 ms	18640 KB	Output is correct
8	Correct	6 ms	18640 KB	Output is correct
9	Correct	7 ms	18640 KB	Output is correct
10	Correct	7 ms	18640 KB	Output is correct
11	Correct	7 ms	18640 KB	Output is correct
12	Correct	7 ms	18640 KB	Output is correct
13	Correct	140 ms	18640 KB	Output is correct
14	Correct	155 ms	20956 KB	Output is correct
15	Correct	154 ms	23288 KB	Output is correct
16	Correct	135 ms	23288 KB	Output is correct
17	Correct	154 ms	26020 KB	Output is correct
18	Correct	155 ms	27620 KB	Output is correct
19	Correct	146 ms	28992 KB	Output is correct
20	Correct	6 ms	28992 KB	Output is correct
21	Correct	7 ms	28992 KB	Output is correct
22	Correct	169 ms	30844 KB	Output is correct
23	Correct	109 ms	30844 KB	Output is correct
24	Correct	210 ms	33604 KB	Output is correct
25	Correct	129 ms	33604 KB	Output is correct

Subtask #2
53.1481481481 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	6 ms	33604 KB	Output isn't correct
2	Correct	7 ms	33604 KB	Output is correct
3	Correct	137 ms	35388 KB	Output is correct
4	Correct	92 ms	37064 KB	Output is correct
5	Correct	95 ms	38480 KB	Output is correct
6	Incorrect	125 ms	43776 KB	Output isn't correct
7	Incorrect	6 ms	43776 KB	Output isn't correct
8	Correct	6 ms	43776 KB	Output is correct
9	Correct	6 ms	43776 KB	Output is correct
10	Correct	6 ms	43776 KB	Output is correct
11	Correct	6 ms	43776 KB	Output is correct
12	Correct	6 ms	43776 KB	Output is correct
13	Correct	6 ms	43776 KB	Output is correct
14	Incorrect	6 ms	43776 KB	Output isn't correct
15	Correct	7 ms	43776 KB	Output is correct
16	Correct	7 ms	43776 KB	Output is correct
17	Correct	6 ms	43776 KB	Output is correct
18	Correct	6 ms	43776 KB	Output is correct
19	Correct	6 ms	43776 KB	Output is correct
20	Correct	6 ms	43776 KB	Output is correct
21	Correct	8 ms	43776 KB	Output is correct
22	Incorrect	6 ms	43776 KB	Output isn't correct
23	Correct	129 ms	44516 KB	Output is correct
24	Correct	171 ms	48528 KB	Output is correct
25	Correct	111 ms	48528 KB	Output is correct
26	Correct	91 ms	48528 KB	Output is correct
27	Correct	85 ms	48528 KB	Output is correct
28	Correct	124 ms	50184 KB	Output is correct
29	Correct	147 ms	51944 KB	Output is correct
30	Incorrect	120 ms	53592 KB	Output isn't correct
31	Correct	179 ms	62548 KB	Output is correct
32	Correct	156 ms	62548 KB	Output is correct
33	Correct	113 ms	62548 KB	Output is correct
34	Correct	94 ms	62548 KB	Output is correct
35	Correct	91 ms	62548 KB	Output is correct
36	Correct	131 ms	62856 KB	Output is correct
37	Incorrect	128 ms	67504 KB	Output isn't correct
38	Correct	173 ms	70304 KB	Output is correct
39	Incorrect	155 ms	70304 KB	Output isn't correct
40	Incorrect	137 ms	70304 KB	Output isn't correct
41	Correct	100 ms	70752 KB	Output is correct
42	Correct	93 ms	72012 KB	Output is correct
43	Correct	87 ms	73508 KB	Output is correct
44	Correct	88 ms	74676 KB	Output is correct
45	Incorrect	139 ms	78084 KB	Output isn't correct
46	Correct	150 ms	79116 KB	Output is correct
47	Incorrect	137 ms	79116 KB	Output isn't correct
48	Correct	198 ms	82628 KB	Output is correct
49	Correct	152 ms	82628 KB	Output is correct
50	Correct	117 ms	82628 KB	Output is correct
51	Correct	120 ms	82628 KB	Output is correct
52	Correct	96 ms	82628 KB	Output is correct
53	Runtime error	127 ms	97020 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Incorrect	149 ms	97020 KB	Output isn't correct

답안 #79877

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 53.1481481481 / 70.0

Subtask #1
30.0 / 30.0

Subtask #2
53.1481481481 / 70.0