oj.uz

Submission #129686

# Submission time Handle Problem Language Result Execution time Memory
129686 2019-07-13T04:37:50 Z 윤교준(#3140) 전압 (JOI14_voltage) C++14
10 / 100
 55 ms 888 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 1005;
const int MAXM = 2005;

vector<int> G[MAXN];

int A[MAXM], B[MAXM];

int N, M, Ans;

bitset<MAXN> chk, isb;
bool dfs(int i, int X) {
	chk[i] = true;
	for(int e : G[i]) {
		int v = A[e]^B[e]^i;
		if(e != X) {
			if(chk[v]) {
				if(isb[v] == isb[i]) return false;
				continue;
			}
			isb[v] = !isb[i];
		} else {
			if(chk[v]) {
				if(isb[v] != isb[i]) return false;
				continue;
			}
			isb[v] = isb[i];
		}
		if(!dfs(v, X)) return false;
	}
	return true;
}
bool isp(int X) {
	chk.reset(); isb.reset();
	for(int i = 1; i <= N; i++) if(!chk[i])
		if(!dfs(i, X)) return false;
	return true;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1; i <= M; i++) {
		cin >> A[i] >> B[i];
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}

	for(int i = 1; i <= M; i++)
		if(isp(i)) Ans++;

	cout << Ans << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 760 KB Output is correct
2 Correct 19 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 22 ms 376 KB Output is correct
5 Correct 39 ms 504 KB Output is correct
6 Correct 55 ms 504 KB Output is correct
7 Correct 40 ms 632 KB Output is correct
8 Correct 19 ms 504 KB Output is correct
9 Correct 27 ms 504 KB Output is correct
10 Correct 36 ms 504 KB Output is correct
11 Correct 12 ms 504 KB Output is correct
12 Correct 34 ms 504 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -