Submission #43843

#	Time	Username	Problem	Language	Result	Execution time	Memory
43843		Bruteforceman	Pipes (BOI13_pipes)	C++11	100 / 100	347 ms	20744 KiB

pipes

#include "bits/stdc++.h"
using namespace std;
bool vis[100010];
int l[500010], r[500010];
vector <int> g[100010];
long long a[100010];
bool del[500010];
int deg[100010];
long long ans[500010];

vector <int> can;
bool bad;
void check(int x) {
	vis[x] = true;
	can.push_back(x);
	int deg = 0;
	for(auto i : g[x]) {
		if(del[i]) continue;
		int y = l[i] ^ r[i] ^ x;
		++deg;
		if(vis[y] == false) check(y);
	}
	if(deg != 2 && deg != 0) {
		bad = true;
	}
}

int edge(int x, int y) {
	for(auto i : g[x]) {
		int p = l[i] ^ r[i] ^ x;
		if(p == y) return i;
	}
	return -1;
}
void solve(vector <int> v) {
	int size = v.size();
	vector <long long> Odd (size), Even (size);
	long long odd = 0;
	long long even = 0;
	long long sum = 0;
	for(int i = 0; i < size; i++) {
		if(i & 1) {
			odd += a[v[i]];
		} else {
			even += a[v[i]];
		}
		Even[i] = even;
		Odd[i] = odd;
		sum += a[v[i]];
	}
	if(sum % 2 != 0) {
		printf("0\n");
		exit(0);
	}
	sum /= 2;
	for(int i = 0; i < size; i++) {
		int p = v[i];
		int q = v[(i + 1) % size];
		int id = edge(p, q);
		if(i & 1) {
			ans[id] = Even[i];
			ans[id] += odd - Odd[i];
		} else {
			ans[id] = Odd[i];
			ans[id] += even - Even[i]; 
		}
		ans[id] = sum - ans[id];
	}
}
int main(int argc, char const *argv[])
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	queue <int> Q;
	for(int i = 1; i <= m; i++) {
		int p, q;
		scanf("%d %d", &p, &q);
		g[p].push_back(i);
		g[q].push_back(i);
		l[i] = p;
		r[i] = q;
	}
	for(int i = 1; i <= n; i++) {
		deg[i] = g[i].size();
		if(g[i].size() == 1) {
			Q.push(i);
		}
	}
	while(!Q.empty()) {
		int p = Q.front();
		Q.pop();
		if(deg[p] != 1) {
			if(a[p] != 0) {
				printf("0\n");
				exit(0);
			}
			continue;
		}
		for(auto i : g[p]) {
			if(del[i] == true) continue;
			int j = l[i] ^ r[i] ^ p;
			deg[j]--;
			if(deg[j] == 1) {
				Q.push(j);
			}
			ans[i] = a[p];
			a[j] -= a[p];
			del[i] = true; 
		}
	}
	for(int i = 1; i <= n; i++) {
		if(vis[i] == false) {
			bad = false;
			can.clear();
			check(i);
			if(can.size() % 2 == 0) {
				bad = true;
			} 
			if(bad) {
				printf("0\n");
				exit(0);
			}
			if(can.size() > 1) {
				solve(can);
			}
		}
	}
	for(int i = 1; i <= m; i++) {
		printf("%lld\n", ans[i] << 1);
	}
	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'int main(int, const char**)':
pipes.cpp:73:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
pipes.cpp:75:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
                       ^
pipes.cpp:80:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
                         ^

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