Submission #243285

#	Time	Username	Problem	Language	Result	Execution time	Memory
243285		anubhavdhar	Pipes (BOI13_pipes)	C++14	100 / 100	470 ms	31892 KiB

pipes

#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 (stderr)

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;
       ^~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70