| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 535377 |
2022-03-10T06:38:48 Z |
faik |
Pipes (BOI13_pipes) |
C++14 |
|
93 ms |
12240 KB |
#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define INF 1000000001
#define LNF 1000000000000000001
#define int ll
typedef long long ll;
typedef pair<int,int> pii;
void solve(){
//#define TEST
int n,m;cin >> n >> m;
if(m > n){
cout << "0";
return;
}
vector<int> netNodeChange(n);
for(int i = 0;i < n;i++){
cin >> netNodeChange[i];
}
vector<int> edgeWeight(m);
vector<vector<pii>> edges(n);
for(int i = 0;i < m;i++){
int a,b;cin >> a >> b;a--;b--;
edges[a].emplace_back(b,i);
edges[b].emplace_back(a,i);
}
//find leafs
queue<int> leafs;
vector<int> neighbourCount(n);
vector<int> removedNodes(n);
for(int i = 0;i < n;i++){
neighbourCount[i] = edges[i].size();
if(edges[i].size() == 1){
leafs.push(i);
}
}
//remove all leafs
while(!leafs.empty()){
int leaf = leafs.front();
leafs.pop();
if(removedNodes[leaf])
continue;
removedNodes[leaf] = true;
pii parent;
for(auto i : edges[leaf]){
if(!removedNodes[i.first])
parent = i;
}
edgeWeight[parent.second] = netNodeChange[leaf]*2;
neighbourCount[leaf]--;
neighbourCount[parent.first]--;
netNodeChange[parent.first] -= netNodeChange[leaf];
if(neighbourCount[parent.first] == 1){
leafs.push(parent.first);
}
if(neighbourCount[parent.first] == 0){
removedNodes[parent.first] = true;
}
}
//find the nodes in the last cycle
vector<int> cycle;
for(int i = 0;i < n;i++){
if(!removedNodes[i])
cycle.push_back(i);
}
//if there is no cycle we are finished
if(cycle.size() == 0){
for(int i : edgeWeight)
cout << i << ' ';
return;
} else if(cycle.size()%2 == 0){//even cycle is bad
cout << '0';
return;
}
int curr = cycle[0];
int next;int nextWeight;
for(auto i : edges[curr]){
if(!removedNodes[i.first]){
next = i.first;
nextWeight = i.second;
}
}
edgeWeight[nextWeight] += 2*netNodeChange[cycle[0]];
netNodeChange[next] -= netNodeChange[cycle[0]];
netNodeChange[cycle[0]] = 0;
int last = cycle[0];
curr = next;
while(curr != cycle[0]){
pii next1;
for(auto i : edges[curr]){
if(!removedNodes[i.first] && i.first != last){
next1 = i;
}
}
edgeWeight[next1.second] += 2*netNodeChange[curr];
netNodeChange[next1.first] -= netNodeChange[curr];
netNodeChange[curr] = 0;
last = curr;
curr = next1.first;
}
if(netNodeChange[cycle[0]] % 2 != 0){
cout << 0;
return;
}
last = next;
curr = cycle[0];
int sign = 1;
bool firstNode = true;
while(curr != cycle[0] || firstNode){
pii next1;
for(auto i : edges[curr]){
if(!removedNodes[i.first] && i.first != last){
next1 = i;
}
}
edgeWeight[next1.second] += netNodeChange[cycle[0]]*sign;
last = curr;
curr = next1.first;
sign = -sign;
firstNode = false;
}
for(int i : edgeWeight)
cout << i << ' ';
}
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
#ifdef DEBUG
freopen("i.txt","r",stdin);
freopen("o.txt","w",stdout);
#endif
int t = 1;
#ifdef TEST
cin >> t;
#endif
while(t--){
solve();
}
return 0;
}
Compilation message
pipes.cpp: In function 'void solve()':
pipes.cpp:92:23: warning: 'nextWeight' may be used uninitialized in this function [-Wmaybe-uninitialized]
92 | edgeWeight[nextWeight] += 2*netNodeChange[cycle[0]];
| ^
pipes.cpp:98:13: warning: 'next' may be used uninitialized in this function [-Wmaybe-uninitialized]
98 | while(curr != cycle[0]){
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
91 ms |
11700 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
54 ms |
9340 KB |
Output is correct |
| 14 |
Correct |
68 ms |
11108 KB |
Output is correct |
| 15 |
Correct |
72 ms |
11716 KB |
Output is correct |
| 16 |
Correct |
82 ms |
9952 KB |
Output is correct |
| 17 |
Correct |
90 ms |
11692 KB |
Output is correct |
| 18 |
Correct |
60 ms |
11680 KB |
Output is correct |
| 19 |
Correct |
65 ms |
11400 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
63 ms |
11716 KB |
Output is correct |
| 23 |
Correct |
51 ms |
9320 KB |
Output is correct |
| 24 |
Correct |
71 ms |
11872 KB |
Output is correct |
| 25 |
Correct |
54 ms |
9816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
53 ms |
11016 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
328 KB |
Output is correct |
| 23 |
Correct |
59 ms |
9860 KB |
Output is correct |
| 24 |
Correct |
84 ms |
12080 KB |
Output is correct |
| 25 |
Correct |
60 ms |
11080 KB |
Output is correct |
| 26 |
Correct |
0 ms |
212 KB |
Output is correct |
| 27 |
Correct |
0 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
1 ms |
212 KB |
Output is correct |
| 30 |
Correct |
70 ms |
11612 KB |
Output is correct |
| 31 |
Correct |
68 ms |
12220 KB |
Output is correct |
| 32 |
Correct |
93 ms |
11768 KB |
Output is correct |
| 33 |
Correct |
78 ms |
11720 KB |
Output is correct |
| 34 |
Correct |
0 ms |
212 KB |
Output is correct |
| 35 |
Correct |
0 ms |
212 KB |
Output is correct |
| 36 |
Correct |
1 ms |
212 KB |
Output is correct |
| 37 |
Correct |
1 ms |
212 KB |
Output is correct |
| 38 |
Correct |
62 ms |
11864 KB |
Output is correct |
| 39 |
Correct |
61 ms |
11588 KB |
Output is correct |
| 40 |
Correct |
73 ms |
11988 KB |
Output is correct |
| 41 |
Correct |
49 ms |
12100 KB |
Output is correct |
| 42 |
Correct |
0 ms |
212 KB |
Output is correct |
| 43 |
Correct |
0 ms |
212 KB |
Output is correct |
| 44 |
Correct |
0 ms |
212 KB |
Output is correct |
| 45 |
Correct |
0 ms |
212 KB |
Output is correct |
| 46 |
Correct |
63 ms |
11796 KB |
Output is correct |
| 47 |
Correct |
74 ms |
12028 KB |
Output is correct |
| 48 |
Correct |
71 ms |
12240 KB |
Output is correct |
| 49 |
Correct |
49 ms |
10704 KB |
Output is correct |
| 50 |
Correct |
0 ms |
212 KB |
Output is correct |
| 51 |
Correct |
0 ms |
212 KB |
Output is correct |
| 52 |
Correct |
0 ms |
212 KB |
Output is correct |
| 53 |
Correct |
0 ms |
212 KB |
Output is correct |
| 54 |
Correct |
69 ms |
11756 KB |
Output is correct |
