oj.uz

Submission #25813

# Submission time Handle Problem Language Result Execution time Memory
25813 2017-06-24T08:06:02 Z kajebiii 전압 (JOI14_voltage) C++14
0 / 100
 149 ms 24016 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10756 KB Output is correct
2 Correct 3 ms 10756 KB Output is correct
3 Correct 6 ms 10760 KB Output is correct
4 Incorrect 3 ms 10760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 20212 KB Output is correct
2 Incorrect 149 ms 20608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 20004 KB Output is correct
2 Incorrect 56 ms 21992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 23056 KB Output is correct
2 Correct 83 ms 24016 KB Output is correct
3 Correct 0 ms 10624 KB Output is correct
4 Incorrect 126 ms 20668 KB Output isn't correct
5 Halted 0 ms 0 KB -