oj.uz

Submission #109201

# Submission time Handle Problem Language Result Execution time Memory
109201 2019-05-05T13:23:27 Z njchung99 전압 (JOI14_voltage) C++14
100 / 100
 227 ms 17528 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
using namespace std;
int n, m;
stack<int> st;
pair<int, int> a[200010];
vector<vector<int>> vt;
int par[100010];
int de[100010];
int visited[100010];
int used[200010];
int dp[100010];
int dp1[100010];
int dap = 0;
int odd = 0;
void dfs(int here) {
	st.push(here);
	visited[here] = 1;
	for (int i = 0; i < vt[here].size(); i++) {
		int id = vt[here][i];
		int next = a[id].first^a[id].second^here;
		if (!visited[next]) {
			used[id] = 1;
			par[next] = here;
			de[next] = de[here] + 1;
			dfs(next);
		}
	}
}
int main()
{
	scanf("%d %d", &n, &m);
	vt.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int q, w;
		scanf("%d %d", &q, &w);
		vt[q].push_back(i);
		vt[w].push_back(i);
		a[i] = { q,w };
	}
	for (int i = 1; i <= n; i++) {
		if(!visited[i])
			dfs(i);
	}
	for (int i = 0; i < m; i++) {
		if (used[i])continue;
		int x = a[i].first;
		int y = a[i].second;
		if (de[x] < de[y])
			swap(x, y);
		if (de[x] % 2 == de[y] % 2) {
			dp[x]++; dp[y]--;
			odd++;
		}
		else {
			dp1[x]++; dp1[y]--;
		}
	}
	if (odd == 1)dap++;
	while (st.size()) {
		int t = st.top();
		int p = par[t];
		st.pop();
		if (par[t] && dp[t]==odd && dp1[t] == 0)dap++;
		dp[p] += dp[t];
		dp1[p] += dp1[t];
	}
	printf("%d\n", dap);
}

Compilation message

voltage.cpp: In function 'void dfs(int)':
voltage.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vt[here].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &q, &w);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 10136 KB Output is correct
2 Correct 142 ms 13244 KB Output is correct
3 Correct 85 ms 10096 KB Output is correct
4 Correct 127 ms 14148 KB Output is correct
5 Correct 9 ms 1536 KB Output is correct
6 Correct 83 ms 12012 KB Output is correct
7 Correct 108 ms 15172 KB Output is correct
8 Correct 183 ms 15224 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9712 KB Output is correct
2 Correct 65 ms 15112 KB Output is correct
3 Correct 44 ms 15048 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 99 ms 10824 KB Output is correct
6 Correct 112 ms 10616 KB Output is correct
7 Correct 127 ms 12536 KB Output is correct
8 Correct 114 ms 13560 KB Output is correct
9 Correct 146 ms 13396 KB Output is correct
10 Correct 115 ms 12352 KB Output is correct
11 Correct 118 ms 10588 KB Output is correct
12 Correct 147 ms 11804 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 12084 KB Output is correct
2 Correct 82 ms 17008 KB Output is correct
3 Correct 7 ms 3584 KB Output is correct
4 Correct 151 ms 13340 KB Output is correct
5 Correct 144 ms 14076 KB Output is correct
6 Correct 154 ms 13276 KB Output is correct
7 Correct 194 ms 15864 KB Output is correct
8 Correct 174 ms 16404 KB Output is correct
9 Correct 192 ms 15060 KB Output is correct
10 Correct 216 ms 16892 KB Output is correct
11 Correct 199 ms 15096 KB Output is correct
12 Correct 182 ms 17024 KB Output is correct
13 Correct 178 ms 14892 KB Output is correct
14 Correct 217 ms 17528 KB Output is correct
15 Correct 227 ms 16888 KB Output is correct
16 Correct 210 ms 16368 KB Output is correct
17 Correct 193 ms 14960 KB Output is correct
18 Correct 152 ms 14980 KB Output is correct