| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 443799 |
2021-07-12T06:27:16 Z |
wind_reaper |
Pipes (BOI13_pipes) |
C++17 |
|
309 ms |
131076 KB |
#include <bits/stdc++.h>
using namespace std;
const int MXN = 100000;
set<array<int, 2>> g[MXN];
int change[MXN], suf[MXN], ans[MXN];
bitset<MXN> vis;
void solve(){
int N, M, x, y;
cin >> N >> M;
for(int i = 0; i < N; i++)
cin >> change[i];
for(int i = 0; i < M; i++){
cin >> x >> y;
--x, --y;
g[x].insert({y, i});
g[x].insert({y, i});
}
if(M > N){
cout << 0 << '\n';
return;
}
queue<array<int, 3>> q;
for(int i = 0; i < N; i++)
if(g[i].size() < 2){
q.push({i, (*g[i].begin())[0], (*g[i].begin())[1]});
vis[i] = 1;
}
int cnt = 0;
while(!q.empty()){
auto [u, par, idx] = q.front();
q.pop();
++cnt;
int t = change[u];
ans[idx] += 2*t;
change[u] -= t;
change[par] -= t;
g[par].erase({u, idx});
if(g[par].size() == 1 && !vis[par])
q.push({par, (*g[par].begin())[0], (*g[par].begin())[1]});
}
if(cnt < N){
if(!((N - cnt) & 1)){
cout << 0 << '\n';
return;
}
for(int i = 0; i < N; i++)
if(!vis[i])
x = i;
int u = x;
vector<int> a, b;
while(u != x || a.empty()){
auto [v, idx] = a.empty() || (*g[u].begin())[0] != a.back() ? *g[u].begin() : *g[u].rbegin();
a.push_back(v);
b.push_back(idx);
u = v;
}
N = a.size();
suf[N-1] = change[a[N-1]];
for(int i = N - 2; i >= 0; --i)
suf[i] = change[a[i]] - suf[i+1];
int pre = 0;
for(int i = 0; i < N; i++){
pre = change[a[i]] - pre;
ans[b[i]] = (pre + (i + 1 < N ? suf[i+1] : 0));
}
}
for(int i = 0; i < M; i++)
cout << ans[i] << '\n';
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
5020 KB |
Output isn't correct |
| 4 |
Incorrect |
49 ms |
11508 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 8 |
Runtime error |
265 ms |
131076 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
271 ms |
131076 KB |
Execution killed with signal 9 |
| 10 |
Incorrect |
4 ms |
5024 KB |
Output isn't correct |
| 11 |
Incorrect |
4 ms |
5024 KB |
Output isn't correct |
| 12 |
Runtime error |
273 ms |
131076 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
304 ms |
131076 KB |
Execution killed with signal 9 |
| 14 |
Incorrect |
47 ms |
11076 KB |
Output isn't correct |
| 15 |
Incorrect |
49 ms |
11556 KB |
Output isn't correct |
| 16 |
Incorrect |
52 ms |
10832 KB |
Output isn't correct |
| 17 |
Incorrect |
48 ms |
11488 KB |
Output isn't correct |
| 18 |
Runtime error |
303 ms |
131076 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
301 ms |
131076 KB |
Execution killed with signal 9 |
| 20 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 21 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 22 |
Runtime error |
301 ms |
131076 KB |
Execution killed with signal 9 |
| 23 |
Incorrect |
39 ms |
10140 KB |
Output isn't correct |
| 24 |
Runtime error |
62 ms |
23112 KB |
Execution killed with signal 11 |
| 25 |
Incorrect |
41 ms |
10360 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
264 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 3 |
Runtime error |
299 ms |
131076 KB |
Execution killed with signal 9 |
| 4 |
Correct |
43 ms |
10144 KB |
Output is correct |
| 5 |
Correct |
43 ms |
10040 KB |
Output is correct |
| 6 |
Correct |
177 ms |
28916 KB |
Output is correct |
| 7 |
Runtime error |
269 ms |
131076 KB |
Execution killed with signal 9 |
| 8 |
Incorrect |
3 ms |
5016 KB |
Output isn't correct |
| 9 |
Runtime error |
8 ms |
9976 KB |
Execution killed with signal 11 |
| 10 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 14 |
Incorrect |
3 ms |
5016 KB |
Output isn't correct |
| 15 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 16 |
Runtime error |
266 ms |
131076 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
270 ms |
131076 KB |
Execution killed with signal 9 |
| 18 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 19 |
Correct |
4 ms |
5024 KB |
Output is correct |
| 20 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 21 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 22 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 23 |
Incorrect |
49 ms |
11756 KB |
Output isn't correct |
| 24 |
Runtime error |
304 ms |
131076 KB |
Execution killed with signal 9 |
| 25 |
Runtime error |
300 ms |
131076 KB |
Execution killed with signal 9 |
| 26 |
Correct |
42 ms |
10156 KB |
Output is correct |
| 27 |
Correct |
43 ms |
10196 KB |
Output is correct |
| 28 |
Correct |
46 ms |
10368 KB |
Output is correct |
| 29 |
Correct |
145 ms |
24216 KB |
Output is correct |
| 30 |
Runtime error |
309 ms |
131076 KB |
Execution killed with signal 9 |
| 31 |
Incorrect |
57 ms |
13084 KB |
Output isn't correct |
| 32 |
Runtime error |
309 ms |
131076 KB |
Execution killed with signal 9 |
| 33 |
Correct |
49 ms |
11448 KB |
Output is correct |
| 34 |
Correct |
43 ms |
10204 KB |
Output is correct |
| 35 |
Correct |
44 ms |
10188 KB |
Output is correct |
| 36 |
Correct |
44 ms |
10192 KB |
Output is correct |
| 37 |
Correct |
178 ms |
28952 KB |
Output is correct |
| 38 |
Runtime error |
302 ms |
131076 KB |
Execution killed with signal 9 |
| 39 |
Incorrect |
60 ms |
13120 KB |
Output isn't correct |
| 40 |
Incorrect |
50 ms |
12948 KB |
Output isn't correct |
| 41 |
Correct |
48 ms |
11212 KB |
Output is correct |
| 42 |
Correct |
42 ms |
9996 KB |
Output is correct |
| 43 |
Correct |
42 ms |
10052 KB |
Output is correct |
| 44 |
Correct |
42 ms |
9932 KB |
Output is correct |
| 45 |
Correct |
162 ms |
26000 KB |
Output is correct |
| 46 |
Incorrect |
48 ms |
12792 KB |
Output isn't correct |
| 47 |
Incorrect |
49 ms |
12836 KB |
Output isn't correct |
| 48 |
Incorrect |
50 ms |
12844 KB |
Output isn't correct |
| 49 |
Incorrect |
56 ms |
11320 KB |
Output isn't correct |
| 50 |
Correct |
42 ms |
10084 KB |
Output is correct |
| 51 |
Correct |
43 ms |
10052 KB |
Output is correct |
| 52 |
Correct |
44 ms |
9896 KB |
Output is correct |
| 53 |
Correct |
160 ms |
26424 KB |
Output is correct |
| 54 |
Incorrect |
48 ms |
12740 KB |
Output isn't correct |
