Submission #24464

#	Time	Username	Problem	Language	Result	Execution time	Memory
24464		Bruteforceman	Tug of War (BOI15_tug)	C++11	0 / 100	19 ms	5320 KiB

tug

#include "bits/stdc++.h"
using namespace std;
bool del[2 * 30005];
int deg[2][30005];
vector <int> g[2][30005];

struct data
{
	int l, r, s;
	data () {}
	data (int l, int r, int s) : l(l), r(r), s(s) {}
} a[2 * 30005];

struct node
{
	int i, side;
	node () {}
	node (int i, int side) : i(i), side(side) {}
};

bool play[2 * 30010];
bool vis[2][30010];
int sum;

bool pl[2 * 30010];
bool vs[2][30010];

void cycle(node n) {
	// cout << n.i << " " << n.side << endl;
	if(n.side == -1) {
		play[n.i] = true;
		if(vis[0][a[n.i].l] == false) {
			cycle(node(a[n.i].l, 0));
			sum += a[n.i].s;
		} else {
			cycle(node(a[n.i].r, 1));
			sum -= a[n.i].s;
		}
	} else {
		vis[n.side][n.i] = true;
		for(auto i : g[n.side][n.i]) {
			if(del[i] == false && play[i] == false) {
				cycle(node(i, -1));
				break;
			}
		}
	}
}
void loop(node n) {
	if(n.side == -1) {
		pl[n.i] = true;
		if(vs[1][a[n.i].r] == false) {
			loop(node(a[n.i].r, 1));
			sum -= a[n.i].s;
		} else {
			loop(node(a[n.i].l, 0));
			sum += a[n.i].s;
		}
	} else {
		vs[n.side][n.i] = true;
		for(auto i : g[n.side][n.i]) {
			if(del[i] == false && pl[i] == false) {
				loop(node(i, -1));
				break;
			}
		}
	}
}

int main(int argc, char const *argv[])
{
	int n, k;
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n+n; i++) {
		int l, r, s;
		scanf("%d %d %d", &l, &r, &s);
		a[i] = data(l, r, s);
		g[0][l].push_back(i);
		g[1][r].push_back(i);
		++deg[0][l];
		++deg[1][r];
	}
	queue <node> Q;
	for(int i = 1; i <= n; i++) {
		if(deg[0][i] == 1) Q.push(node(i, 0));
		if(deg[1][i] == 1) Q.push(node(i, 1));
		
		if(deg[0][i] == 0 || deg[1][i] == 0) {
			printf("NO\n");
			exit(0);
		}
	}
	int add[2];
	add[0] = add[1] = 0;
	while(!Q.empty()) {
		node p = Q.front();
		Q.pop();
		for(auto i : g[p.side][p.i]) {
			if(del[i] == false) {
				add[p.side] += a[i].s;
				del[i] = true;
				if(p.side == 0) {
					--deg[1][a[i].r];
					if(deg[1][a[i].r] == 1) {
						Q.push(node(a[i].r, 1));
					}
					if(deg[1][a[i].r] == 0) {
						printf("NO\n");
						exit(0);
					}
				} else {
					--deg[0][a[i].l];
					if(deg[0][a[i].l] == 1) {
						Q.push(node(a[i].l, 0));
					}
					if(deg[0][a[i].l] == 0) {
						printf("NO\n");
						exit(0);
					}
				}
			}
		}
	}
	for(int i = 1; i <= n+n; i++) {
		if(play[i] == false) {
			int k1, k2;
			sum = 0;
			cycle(node(i, -1));
			k1 = sum;
			sum = 0;
			loop(node(i, -1));
			k2 = sum;
			assert(k1 == -k2);
		}
	} 
	return 0; 
}

Compilation message (stderr)

tug.cpp: In function 'int main(int, const char**)':
tug.cpp:73:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
                        ^
tug.cpp:76:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &l, &r, &s);
                                ^

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 23
• Subtask 4: 0 / 29