제출 #196966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
196966		mahmoudbadawy	Pipes (BOI13_pipes)	C++17	100 / 100	275 ms	29432 KiB

pipes

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int M=5e5+5;
const int N=1e5+5;

int n,m;
int ans[M],arr[N],co[N];
vector<pair<int,int> > adj[N];
int cur;
vector<pair<int,int> > adj2[M];
int vis[N];

int dfs1(int node,int p,int co,int pa)
{
	if(co==cur) return 0;
	for(auto i:adj2[node])
	{
		if(i.F==pa) continue;
		return i.S*p+dfs1(i.F,-1*p,co+1,node);
	}
}

void dfs2(int node,int co,int pa)
{
	if(co==cur) return;
	for(auto i:adj2[node])
	{
		if(i.F==pa) continue;
		ans[i.F]=i.S-ans[node];
		dfs2(i.F,co+1,node);
	}
}

int main()
{
	cin >> n >> m;
	if(m>n)
	{
		cout << 0 << endl;
		return 0;
	}
	for(int i=1;i<=n;i++)
		cin >> arr[i];
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin >> x >> y;
		adj[x].emplace_back(y,i);
		adj[y].emplace_back(x,i);
		co[x]++; co[y]++;
	}
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		if(adj[i].size()==1) q.push(i);
	}
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		vis[x]=1;
		int to=-1,ed=-1;
		for(int i=0;i<adj[x].size();i++)
		{
			co[adj[x][i].F]--;
			if(!vis[adj[x][i].F])
			{
				to=adj[x][i].F; ed=adj[x][i].S;
			}
			arr[adj[x][i].F]-=arr[x];
		}
		if(to!=-1)
		{
			ans[ed]=2*arr[x];
			if(co[to]==1)
				q.push(to);
		}
	}
	int mn=-1;
	for(int i=1;i<=n;i++)
	{
		if(vis[i]) continue;
		vector<int> te;
		for(auto x:adj[i])
		{
			if(!vis[x.F]) te.push_back(x.S);
		}
		assert(te.size()==2);
		//eq.push_back({{min(te[0],te[1]),max(te[0],te[1])},arr[i]});
		adj2[te[0]].emplace_back(te[1],2*arr[i]);
		adj2[te[1]].emplace_back(te[0],2*arr[i]);
		if(mn==-1) mn=te[0];
		cur++;
	}
	if(cur%2==0&&cur)
	{
		cout << 0 << endl;
		return 0;
	}
	if(cur){
		int a=dfs1(mn,1,0,-1);
		a/=2;
		ans[mn]=a;
		dfs2(mn,0,-1);
	}
	for(int i=0;i<m;i++)
		printf("%d\n",ans[i]);
}

컴파일 시 표준 에러 (stderr) 메시지

pipes.cpp: In function 'int main()':
pipes.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<adj[x].size();i++)
               ~^~~~~~~~~~~~~~
pipes.cpp: In function 'int dfs1(int, int, int, int)':
pipes.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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