Submission #25813

#	Time	Username	Problem	Language	Result	Execution time	Memory
25813		kajebiii	전압 (JOI14_voltage)	C++14	0 / 100	149 ms	24016 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;

int N, M;
vector<int> Ed[MAX_N];

int Ix[MAX_N], IN, C[MAX_N];
int Deg[MAX_N], BDeg[MAX_N];
vector<pi> Bad, Good, All;
vector<int> Bs[MAX_N], Gs[MAX_N];
void dfs(int v, int c) {
	C[v] = c;
	Ix[v] = ++IN;
	for(int w : Ed[v]) if(Ix[w] == 0) dfs(w, 3-c);
}
int main() {
	cin >> N >> M;
	for(int i=0; i<M; i++) {
		int x, y; scanf("%d%d", &x, &y);
		All.push_back(pi(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, 1);

	for(int v=1; v<=N; v++) {
		for(int w : Ed[v]) {
			if(C[v] + C[w] == 3) {
				Deg[v]++; Gs[v].push_back(w);
				if(v < w) Good.push_back(pi(v, w));
			}else {
				BDeg[v]++; Bs[v].push_back(w);
				if(v < w) Bad.push_back(pi(v, w));
			}
		}
	}
	int sN = SZ(Bad);
//	printf("[BAD]\n");for(pi &e : Bad) printf("[%d %d] ", e.one, e.two); puts("");
//	printf("[Good]\n");for(pi &e : Good) printf("[%d %d] ", e.one, e.two); puts("");
	if(sN == 0) {
		int ans = 0;
		for(pi &e : All) {
			int x, y; tie(x, y) = e;
			if(Deg[x] == 1 || Deg[y] == 1) ans++;
		}
		printf("%d\n", ans);
	} else {
		int ans = 0;
		if(sN == 1) ans++;
		set<pi> S;
		for(int i=1; i<=N; i++) {
			if(Deg[i] == 1 && BDeg[i] == sN) {
				pi e = pi(i, Gs[i][0]);
				if(e.one > e.two) swap(e.one, e.two);
				S.insert(e);
				int v = Gs[i][0], w = i;
				while(Deg[v] == 2) {
					int t = -1;
					for(int k=0; k<2; k++) if(Gs[v][k] != w) t = Gs[v][k];
					w = v; v = t;
					e = pi(v, w);
					if(e.one > e.two) swap(e.one, e.two);
					S.insert(e);
				}
			}
		}
		printf("%d\n", ans + (int)S.size());
	}
	return 0;
}

Compilation message (stderr)

voltage.cpp: In function 'int main()':
voltage.cpp:33: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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 35
• Subtask 4: 0 / 45