Submission #25768

#	Time	Username	Problem	Language	Result	Execution time	Memory
25768		kdh9949	전압 (JOI14_voltage)	C++14	100 / 100	339 ms	22672 KiB

voltage

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

struct E{ int x, i; };

int n, m, vis[100010], cr, d[100010], ps[100010], pe[100010], cnt, dc, fl, ans;
vector<E> e[100010];
vector<int> t[100010];

void T_T(){ puts("0"); exit(0); }

void col(int x, int c){
	vis[x] = c;
	for(auto &i : e[x]){
		if(vis[i.x] && vis[i.x] != 3 - c) fl = 0;
		else if(!vis[i.x]) col(i.x, 3 - c);
	}
}

const int sz = 131072;
struct Seg{
	int dat[2 * sz];
	void upd(int x, int v){ for(x += sz; x; x /= 2) dat[x] += v; }
	int get(int s, int e){
		int ret = 0;
		for(s += sz, e += sz; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1) ret += dat[s++];
			if(e % 2 == 0) ret += dat[e--];
		}
		return ret;
	}
} S[2];

void g(int x, int p){
	vis[x] = 1;
	ps[x] = ++cnt;
	for(auto &i : e[x]){
		if(i.i == p) continue;
		if(vis[i.x] && d[i.x] < d[x]){
			int t = (d[i.x] + d[x]) & 1;
			if(!t) dc++;
			S[t].upd(ps[i.x], -1);
			S[t].upd(ps[x], 1);
		}
		else if(!vis[i.x]){
			t[x].push_back(i.x);
			d[i.x] = d[x] + 1;
			g(i.x, i.i);
		}
	}
	pe[x] = cnt;
}

void f(int x){
	for(auto &i : t[x]){
		f(i);
		int t0 = S[0].get(ps[i], pe[i]);
		int t1 = S[1].get(ps[i], pe[i]);
		if(t0 == dc && !t1) ans++;
	}
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0, x, y; i < m; i++){
		scanf("%d%d", &x, &y);
		e[x].push_back({y, i});
		e[y].push_back({x, i});
	}
	for(int i = 1; i <= n; i++){
		if(!vis[i]){
			fl = 1;
			col(i, 1);
			if(!fl){
				if(cr) T_T();
				cr = i;
			}
		}
	}
	fill(vis + 1, vis + n + 1, 0);
	if(!cr){
		int rans = 0;
		for(int i = 1; i <= n; i++){
			if(vis[i]) continue;
			ans = dc = 0;
			g(i, -1);
			if(dc > 1) ans = 0;
			else if(dc == 1) ans = 1;
			f(i);
			rans += ans;
		}
		printf("%d\n", rans);
	}
	else{
		g(cr, -1);
		if(dc > 1) ans = 0;
		else if(dc == 1) ans = 1;
		f(cr);
		printf("%d\n", ans);
	}
}

Compilation message (stderr)

voltage.cpp: In function 'int main()':
voltage.cpp:64:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
voltage.cpp:66:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45