제출 #6010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6010		ainta	전압 (JOI14_voltage)	C++98	100 / 100	144 ms	13520 KiB

voltage

#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct A{
	int a, b;
}tp;
vector<A>E[100010];
int n, m, Dep[100010], par[100010], S, D[100010], Res, ord[100010], cnt;
bool v[100010], chk[200010];
void DFS(int a)
{
	ord[++cnt] = a;
	int i;
	Dep[a] = Dep[par[a]] + 1;
	v[a] = true;
	for (i = 0; i < E[a].size(); i++){
		if (!v[E[a][i].a]){
			chk[E[a][i].b] = true;
			par[E[a][i].a] = a;
			DFS(E[a][i].a);
		}
	}
}
int main()
{
	int i, a, b, j, ck;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i++){
		scanf("%d%d", &a, &b);
		tp.a = b, tp.b = i;
		E[a].push_back(tp);
		tp.a = a;
		E[b].push_back(tp);
	}
	for (i = 1; i <= n; i++){
		if (!v[i]){
			DFS(i);
		}
	}
	for (i = 1; i <= n; i++){
		for (j = 0; j < E[i].size(); j++){
			if (!chk[E[i][j].b]){
				chk[E[i][j].b] = true;
				ck = -1;
				if ((Dep[i] + Dep[E[i][j].a]) % 2 == 0){
					S++;
					ck = 1;
				}
				a = E[i][j].a, b = i;
				if (Dep[i] > Dep[E[i][j].a])swap(a, b);
				D[a] += ck, D[b] += -ck;
			}
		}
	}
	if (S == 1)Res++;
	for (i = cnt; i >= 1; i--){
		a = ord[i];
		D[par[a]] += D[a];
		if (D[a] == S && par[a]){
			Res++;
		}
	}
	printf("%d\n", Res);
}

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