Submission #25818

#	Time	Username	Problem	Language	Result	Execution time	Memory
25818		kajebiii	전압 (JOI14_voltage)	C++14	100 / 100	343 ms	31028 KiB

voltage

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 1e5 + 100, LOG_N = 20;

int N, M;
vector<int> Ed[MAX_N], Tr[MAX_N];
int P[LOG_N][MAX_N], Ix[MAX_N], IN, Co[MAX_N], D[MAX_N];
vector<pi> List;
void dfs(int v, int p) {
	P[0][v] = p;
	Ix[v] = ++IN;
	Co[v] = 1 - Co[p]; D[v] = D[p] + 1;
	for(int w : Ed[v]) {
		if(Ix[w] == 0) dfs(w, v), Tr[v].push_back(w);
		else if(Ix[v] < Ix[w]) List.push_back(pi(v, w));
	}
}
int getLCA(int a, int b) {
	if(D[a] < D[b]) swap(a, b);
	for(int p=0; p<LOG_N; p++) if((D[a] - D[b]) & (1<<p)) a = P[p][a];
	if(a == b) return a;
	for(int p=LOG_N-1; p>=0; p--) if(P[p][a] != P[p][b])
		a = P[p][a], b = P[p][b];
	return P[0][a];
}
int Val[MAX_N];
void getUp(int v, int p) {
	for(int w : Tr[v]) {
		getUp(w, v);
		Val[v] += Val[w];
	}
}
int main() {
	cin >> N >> M;
	for(int i=0; i<M; i++) {
		int x, y; scanf("%d%d", &x, &y);
		Ed[x].push_back(y);
		Ed[y].push_back(x);
	}
	for(int i=1; i<=N; i++) if(Ix[i] == 0) dfs(i, 0);
	for(int p=1; p<LOG_N; p++) for(int i=1; i<=N; i++) P[p][i] = P[p-1][P[p-1][i]];

	int same = 0;
	for(pi &e : List) {
		int x, y; tie(x, y) = e;
		int val = -1;
		if(Co[x] == Co[y]) val = +1, same++;
		int l = getLCA(x, y);
		Val[x] += val; Val[y] += val; Val[l] -= val * 2;
	}
	for(int i=1; i<=N; i++) if(P[0][i] == 0) getUp(i, 0);

	int ans = 0;
	if(same == 1) ans++;
	for(int i=1; i<=N; i++) if(P[0][i] != 0)
		if(Val[i] == same) ans++;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

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