| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 78936 | 2018-10-09T16:35:57 Z | Charis02 | Pipes (BOI13_pipes) | C++14 | 322 ms | 29372 KB |
/*
solution is the same as described here: https://boi2013.informatik-olympiade.de/wp-content/uploads/2013/05/pipes-spoiler.pdf
*/
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#include<stack>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 100004
#define INF 1e9+7
using namespace std;
ll n,m,ar[N],val[N],deg[N];
bool vis[N],cycle;
vector < vector < pi > > graph(N);
vector < pi > neo;
void solvetree(ll cur,ll par,ll edge)
{
rep(i,0,graph[cur].size())
{
ll v = graph[cur][i].first;
if(v == par)
continue;
solvetree(v,cur,graph[cur][i].second);
ar[cur] -= val[graph[cur][i].second];
}
val[edge] = ar[cur];
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> n >> m;
rep(i,1,n+1)
{
cin >> ar[i];
}
rep(i,0,m)
{
ll a,b;
cin >> a >> b;
graph[a].push_back(mp(b,i));
graph[b].push_back(mp(a,i));
}
if(m > n)
{
cout << 0 << endl;
return 0;
}
else if(m == n-1)
{
solvetree(1,1,m);
rep(i,0,m)
{
cout << 2*val[i] << endl;
}
}
else
{
ll nodes = n;
stack < pi > s;
rep(i,1,n+1)
{
deg[i] = graph[i].size();
if(deg[i] == 1)
{
vis[i] = true;
s.push(mp(i,graph[i][0].second));
}
}
while(!s.empty())
{
nodes--;
ll cur = s.top().first;
ll e = s.top().second;
s.pop();
deg[cur]--;
// cout << cur << " " << e << endl;
val[e] = ar[cur];
// cout << deg[1] <<endl;
rep(i,0,graph[cur].size())
{
ll v = graph[cur][i].first;
if(deg[v] <= 1)
continue;
ar[v] -= val[e];
deg[v]--;
graph[v].erase(find(graph[v].begin(),graph[v].end(),mp(cur,graph[cur][i].second)));
// cout << v << " " << deg[v] << endl;
if(deg[v] == 1)
{
vis[v] = true;
s.push(mp(v,graph[v][0].second));
}
}
}
ll st = 1;
while(vis[st])
{
st++;
}
ll start = st;
while(!vis[start])
{
pi potential;
bool found = false;
rep(i,0,graph[st].size())
{
ll v = graph[st][i].first;
if(!vis[v])
{
if(v == start)
{
potential = mp(st,graph[st][i].second);
continue;
}
found = true;
neo.push_back(mp(st,graph[st][i].second));
vis[v] = true;
st = v;
break;
}
}
if(!found)
{
vis[start] = true;
neo.push_back(potential);
st = start;
}
}
if((neo.size())%2==0)
{
cout << 0 << endl;
}
else
{
ll s = 0;
rep(i,0,neo.size())
{
s += ar[neo[i].first]*pow(-1,i%2);
}
val[neo[neo.size()-1].second] = s/2;
val[neo[0].second] = ar[neo[0].first] - s/2;
rep(i,1,neo.size()-1)
{
val[neo[i].second] =ar[neo[i].first] - val[neo[i-1].second];
}
rep(i,0,m)
{
cout << 2*val[i] << endl;
}
}
}
return 0;
}
/*
3 3
1 3 2
1 2
1 3
2 3
4 4
1 3 2 0
4 1
1 2
1 3
2 3
5 5
1 3 2 -4 0
5 1
1 2
4 3
2 3
2 4
*/
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 2808 KB | Output is correct |
| 2 | Correct | 4 ms | 2812 KB | Output is correct |
| 3 | Correct | 6 ms | 3012 KB | Output is correct |
| 4 | Correct | 237 ms | 10020 KB | Output is correct |
| 5 | Correct | 4 ms | 10020 KB | Output is correct |
| 6 | Correct | 5 ms | 10020 KB | Output is correct |
| 7 | Correct | 4 ms | 10020 KB | Output is correct |
| 8 | Correct | 4 ms | 10020 KB | Output is correct |
| 9 | Correct | 6 ms | 10020 KB | Output is correct |
| 10 | Correct | 6 ms | 10020 KB | Output is correct |
| 11 | Correct | 6 ms | 10020 KB | Output is correct |
| 12 | Correct | 6 ms | 10020 KB | Output is correct |
| 13 | Correct | 193 ms | 10020 KB | Output is correct |
| 14 | Correct | 221 ms | 10020 KB | Output is correct |
| 15 | Correct | 233 ms | 10304 KB | Output is correct |
| 16 | Correct | 242 ms | 10304 KB | Output is correct |
| 17 | Correct | 239 ms | 10304 KB | Output is correct |
| 18 | Correct | 272 ms | 10304 KB | Output is correct |
| 19 | Correct | 247 ms | 13172 KB | Output is correct |
| 20 | Correct | 5 ms | 13172 KB | Output is correct |
| 21 | Correct | 6 ms | 13172 KB | Output is correct |
| 22 | Correct | 322 ms | 13172 KB | Output is correct |
| 23 | Correct | 192 ms | 13172 KB | Output is correct |
| 24 | Correct | 245 ms | 13172 KB | Output is correct |
| 25 | Correct | 201 ms | 13172 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 ms | 13172 KB | Output is correct |
| 2 | Correct | 6 ms | 13172 KB | Output is correct |
| 3 | Correct | 84 ms | 13172 KB | Output is correct |
| 4 | Correct | 68 ms | 13172 KB | Output is correct |
| 5 | Correct | 99 ms | 13172 KB | Output is correct |
| 6 | Correct | 297 ms | 29372 KB | Output is correct |
| 7 | Correct | 6 ms | 29372 KB | Output is correct |
| 8 | Correct | 4 ms | 29372 KB | Output is correct |
| 9 | Correct | 4 ms | 29372 KB | Output is correct |
| 10 | Correct | 4 ms | 29372 KB | Output is correct |
| 11 | Correct | 5 ms | 29372 KB | Output is correct |
| 12 | Correct | 4 ms | 29372 KB | Output is correct |
| 13 | Correct | 4 ms | 29372 KB | Output is correct |
| 14 | Correct | 4 ms | 29372 KB | Output is correct |
| 15 | Correct | 6 ms | 29372 KB | Output is correct |
| 16 | Correct | 6 ms | 29372 KB | Output is correct |
| 17 | Correct | 4 ms | 29372 KB | Output is correct |
| 18 | Correct | 4 ms | 29372 KB | Output is correct |
| 19 | Correct | 5 ms | 29372 KB | Output is correct |
| 20 | Correct | 5 ms | 29372 KB | Output is correct |
| 21 | Correct | 6 ms | 29372 KB | Output is correct |
| 22 | Correct | 8 ms | 29372 KB | Output is correct |
| 23 | Correct | 206 ms | 29372 KB | Output is correct |
| 24 | Correct | 255 ms | 29372 KB | Output is correct |
| 25 | Correct | 81 ms | 29372 KB | Output is correct |
| 26 | Correct | 66 ms | 29372 KB | Output is correct |
| 27 | Correct | 70 ms | 29372 KB | Output is correct |
| 28 | Correct | 65 ms | 29372 KB | Output is correct |
| 29 | Correct | 235 ms | 29372 KB | Output is correct |
| 30 | Correct | 244 ms | 29372 KB | Output is correct |
| 31 | Correct | 248 ms | 29372 KB | Output is correct |
| 32 | Correct | 250 ms | 29372 KB | Output is correct |
| 33 | Correct | 86 ms | 29372 KB | Output is correct |
| 34 | Correct | 65 ms | 29372 KB | Output is correct |
| 35 | Correct | 65 ms | 29372 KB | Output is correct |
| 36 | Correct | 64 ms | 29372 KB | Output is correct |
| 37 | Correct | 285 ms | 29372 KB | Output is correct |
| 38 | Correct | 246 ms | 29372 KB | Output is correct |
| 39 | Correct | 239 ms | 29372 KB | Output is correct |
| 40 | Correct | 246 ms | 29372 KB | Output is correct |
| 41 | Correct | 84 ms | 29372 KB | Output is correct |
| 42 | Correct | 68 ms | 29372 KB | Output is correct |
| 43 | Correct | 66 ms | 29372 KB | Output is correct |
| 44 | Correct | 65 ms | 29372 KB | Output is correct |
| 45 | Correct | 228 ms | 29372 KB | Output is correct |
| 46 | Correct | 265 ms | 29372 KB | Output is correct |
| 47 | Correct | 249 ms | 29372 KB | Output is correct |
| 48 | Correct | 255 ms | 29372 KB | Output is correct |
| 49 | Correct | 83 ms | 29372 KB | Output is correct |
| 50 | Correct | 66 ms | 29372 KB | Output is correct |
| 51 | Correct | 62 ms | 29372 KB | Output is correct |
| 52 | Correct | 69 ms | 29372 KB | Output is correct |
| 53 | Correct | 246 ms | 29372 KB | Output is correct |
| 54 | Correct | 261 ms | 29372 KB | Output is correct |