Submission #111635

#	Time	Username	Problem	Language	Result	Execution time	Memory
111635		wilwxk	Pipes (BOI13_pipes)	C++11	74.07 / 100	478 ms	27424 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=2e5+5;
vector<int> g[MAXN], lista[MAXN];
vector<int> ncyc;
ll v[MAXN], tenho[MAXN];
int gin[MAXN];
ll resp[MAXN], soma;
int n, m;

void poda() {
	queue<int> qu;
	for(int i=1; i<=n; i++) if(gin[i]==1) qu.push(i);
	while(!qu.empty()) {
		int cur=qu.front(); qu.pop();
		gin[cur]=0; ncyc.push_back(cur);
		for(int i=0; i<g[cur].size(); i++) {
			int viz=g[cur][i]; int ind=lista[cur][i];
			if(!gin[viz]) continue;
			gin[viz]--;
			if(gin[viz]<=1) qu.push(viz);
			resp[ind]=v[cur]-tenho[cur];
			tenho[viz]+=resp[ind];
			tenho[cur]+=resp[ind];
			// printf("%d -> %d (%d, %lld)\n", cur, viz, ind, tenho[cur]);
		}
	}
}

void dfs(int cur, int k) {
	// printf("%d %d\n", cur, k);
	gin[cur]=1;
	for(int i=0; i<g[cur].size(); i++) {
		int viz=g[cur][i]; int ind=lista[cur][i];
		if(gin[viz]!=2) continue;
		dfs(viz, k^1);
	}
	if(!k) soma+=v[cur];
	else soma-=v[cur];
}

void solve(int cur, int p, int ori) {
	gin[cur]=2;
	// printf("solve %d %d\n", cur, tenho[cur]);
	for(int i=0; i<g[cur].size(); i++) {
		int viz=g[cur][i]; int ind=lista[cur][i];
		if(viz==p||gin[viz]==0) continue;
		if(cur==p) resp[ind]=soma;
		else resp[ind]=v[cur]-tenho[cur];
		tenho[viz]+=resp[ind];
		tenho[cur]+=resp[ind];
		// printf("%d -> %d (%d)\n", cur, viz, tenho[cur]);
		if(viz!=ori) solve(viz, cur, ori);
		if(cur==ori) break;
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%lld", &v[i]), v[i]*=2;
	for(int i=1; i<=m; i++) {
		int a, b; scanf("%d %d", &a, &b);
		g[a].push_back(b); g[b].push_back(a);
		gin[a]++; gin[b]++;
		lista[a].push_back(i); lista[b].push_back(i);
	}

	poda();
	for(int i=1; i<=n; i++) if(gin[i]) v[i]-=tenho[i], tenho[i]=0;
	// for(int i=1; i<=n; i++) cout << tenho[i] << " " << v[i] << endl;
	// for(auto cur : ncyc) printf("C %d\n", cur);

	if(m>n||(n-ncyc.size())%2==0) {
		printf("0\n");
		return 0;
	}
	if(m==n-1&&tenho[ncyc.back()]!=v[ncyc.back()]) {
		printf("0\n");
		return 0;
	}

	for(int i=1; i<=n; i++) {
		if(!gin[i]) continue;
		dfs(i, 0);	
		// printf("ok %lld\n", soma);
		solve(i, i, i);
		break;
	}

	bool ok=1;
	for(int i=1; i<=n; i++) if(gin[i]&&tenho[i]!=v[i]) ok=0;
	// for(int i=1; i<=n; i++) cout << tenho[i] << " " << v[i] << endl;

	if(ok) {
		for(int i=1; i<=m; i++) printf("%lld\n", resp[i]);
	}
	else {
		printf("0\n");
	}

}

Compilation message (stderr)

pipes.cpp: In function 'void poda()':
pipes.cpp:19:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~
pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<g[cur].size(); i++) {
               ~^~~~~~~~~~~~~~
pipes.cpp:36:26: warning: unused variable 'ind' [-Wunused-variable]
   int viz=g[cur][i]; int ind=lista[cur][i];
                          ^~~
pipes.cpp: In function 'void solve(int, int, int)':
pipes.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<g[cur].size(); i++) {
               ~^~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:62:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%lld", &v[i]), v[i]*=2;
                          ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
pipes.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

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