#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()
using namespace std;
const short int __PRECISION = 10;
const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 2e5+5;
const ll ROOTN = 320;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
int N, M;
int main()
{
/*
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
*/
cin>>N>>M;
if(M > N)
{
puts("0");
exit(0);
}
ll c[N+1], sum = 0;
int dep[N+1], weight[M+1], par[N+1], j, k;
bool vis[N+1];
set<pair<int, int>> g[N+1];
F0Re(i, N)
cin>>c[i], vis[i] = false, sum += c[i];
sum /= 2;
map<pair<int, int>, int> index;
F0R(i, M)
{
cin>>j>>k;
g[j].insert(mp(k, i));
g[k].insert(mp(j, i));
index[mp(j, k)] = index[mp(k, j)] = i;
}
// dbgLine;
dep[1] = 0;
vis[1] = true;
par[1] = -1;
queue<int> Q;
Q.push(1);
while(!Q.empty())
{
int a = Q.front();
Q.pop();
for(pair<int, int> p : g[a])
{
if(vis[p.ff] and dep[p.ff] != dep[a] and p.ff != par[a])
{
puts("0");
exit(0);
}
if(!vis[p.ff])
{
vis[p.ff] = true;
dep[p.ff] = dep[a] + 1;
Q.push(p.ff);
par[p.ff] = a;
}
}
}
// dbgLine;
set<int> assigned;
F0Re(i, N)
if(g[i].size() == 1)
Q.push(i);
// dbgLine;
while(!Q.empty())
{
int a = Q.front();
Q.pop();
if(g[a].size() == 0)
continue;
int b = g[a].begin()->ff, i = g[a].begin()->ss;
// cout<<"in for a = "<<a<<" and b = "<<b<<endl;
g[a].erase(mp(b, i));
if(g[b].size() == 0)
continue;
g[b].erase(mp(a, i));
weight[i] = c[a];
c[b] -= c[a];
sum -= c[a];
// dbgLine;
assigned.insert(i);
if(g[b].size() == 1)
Q.push(b);
// dbgLine;
}
// dbgLine;
int cycle_size = M - assigned.size();
// cout<<cycle_size<<endl;
if(cycle_size)
{
int node, next[N+1], pre[N+1], tmp = 0;
F0Re(i, N)
next[i] = -1, pre[i] = -1;
F0Re(i, N)
if(g[i].size() != 0)
{
node = i;
break;
}
next[node] = g[node].begin()->ff;
pre[g[node].begin()->ff] = node;
node = next[node];
while(next[node] == -1)
next[node] = g[node].begin()->ff + g[node].rbegin()->ff - pre[node]/*, cout<<"set next["<<node<<"] = "<<next[node]<<'\n'*/,
pre[next[node]] = node, node = next[node];
F0R(i, cycle_size/2 + 1)
node = next[next[node]], tmp += c[node];
F0R(i, cycle_size)
{
weight[index[mp(node,next[node])]] = tmp - sum;
tmp += c[next[next[node]]] - c[next[node]];
node = next[next[node]];
}
}
// dbgLine;
F0R(i, M)
cout<<2*weight[i]<<'\n';
return 0;
}
Compilation message
pipes.cpp: In function 'int main()':
pipes.cpp:137:7: warning: 'node' may be used uninitialized in this function [-Wmaybe-uninitialized]
int node, next[N+1], pre[N+1], tmp = 0;
^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
7 ms |
640 KB |
Output is correct |
4 |
Correct |
407 ms |
31128 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
6 ms |
640 KB |
Output is correct |
10 |
Correct |
7 ms |
640 KB |
Output is correct |
11 |
Correct |
7 ms |
640 KB |
Output is correct |
12 |
Correct |
7 ms |
640 KB |
Output is correct |
13 |
Correct |
385 ms |
24828 KB |
Output is correct |
14 |
Correct |
384 ms |
29432 KB |
Output is correct |
15 |
Correct |
388 ms |
31168 KB |
Output is correct |
16 |
Correct |
331 ms |
26604 KB |
Output is correct |
17 |
Correct |
389 ms |
31024 KB |
Output is correct |
18 |
Correct |
406 ms |
31304 KB |
Output is correct |
19 |
Correct |
366 ms |
30968 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
6 ms |
640 KB |
Output is correct |
22 |
Correct |
389 ms |
31172 KB |
Output is correct |
23 |
Correct |
308 ms |
24824 KB |
Output is correct |
24 |
Correct |
470 ms |
31224 KB |
Output is correct |
25 |
Correct |
333 ms |
26044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
3 |
Correct |
234 ms |
28408 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
256 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
256 KB |
Output is correct |
13 |
Correct |
5 ms |
256 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
7 ms |
640 KB |
Output is correct |
16 |
Correct |
6 ms |
640 KB |
Output is correct |
17 |
Correct |
6 ms |
640 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
256 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
7 ms |
640 KB |
Output is correct |
23 |
Correct |
348 ms |
25976 KB |
Output is correct |
24 |
Correct |
450 ms |
31864 KB |
Output is correct |
25 |
Correct |
245 ms |
28536 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
4 ms |
384 KB |
Output is correct |
28 |
Correct |
5 ms |
384 KB |
Output is correct |
29 |
Correct |
4 ms |
384 KB |
Output is correct |
30 |
Correct |
394 ms |
31224 KB |
Output is correct |
31 |
Correct |
390 ms |
31736 KB |
Output is correct |
32 |
Correct |
408 ms |
31868 KB |
Output is correct |
33 |
Correct |
267 ms |
30204 KB |
Output is correct |
34 |
Correct |
5 ms |
384 KB |
Output is correct |
35 |
Correct |
4 ms |
384 KB |
Output is correct |
36 |
Correct |
5 ms |
384 KB |
Output is correct |
37 |
Correct |
5 ms |
384 KB |
Output is correct |
38 |
Correct |
384 ms |
31864 KB |
Output is correct |
39 |
Correct |
397 ms |
31864 KB |
Output is correct |
40 |
Correct |
392 ms |
31864 KB |
Output is correct |
41 |
Correct |
268 ms |
30076 KB |
Output is correct |
42 |
Correct |
5 ms |
384 KB |
Output is correct |
43 |
Correct |
5 ms |
384 KB |
Output is correct |
44 |
Correct |
4 ms |
384 KB |
Output is correct |
45 |
Correct |
5 ms |
384 KB |
Output is correct |
46 |
Correct |
386 ms |
31868 KB |
Output is correct |
47 |
Correct |
425 ms |
31892 KB |
Output is correct |
48 |
Correct |
406 ms |
31864 KB |
Output is correct |
49 |
Correct |
259 ms |
28404 KB |
Output is correct |
50 |
Correct |
4 ms |
384 KB |
Output is correct |
51 |
Correct |
4 ms |
384 KB |
Output is correct |
52 |
Correct |
5 ms |
432 KB |
Output is correct |
53 |
Correct |
5 ms |
384 KB |
Output is correct |
54 |
Correct |
382 ms |
31480 KB |
Output is correct |