oj.uz

Submission #43352

# Submission time Handle Problem Language Result Execution time Memory
43352 2018-03-14T04:54:51 Z ffresh 전압 (JOI14_voltage) C++14
100 / 100
 174 ms 54596 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+15,M = 2e5+15;

vector<int> adj[N];

int dp2[N],dp[N],depth[N];

bool vis[N];
stack<int> st;

int parent[N];

int a[M],b[M];

bool used[M];
void dfs(int root){
	vis[root]= 1;

	st.push(root);

	for(int i=0;i<adj[root].size();++i){
		int id = adj[root][i];
		int u = a[id]^b[id]^root;
		if(!vis[u]){
			used[id]= 1;
			parent[u] = root;
			depth[u] = depth[root]+1;
			dfs(u);
		}
	}
}

int main(){
	//freopen("input.txt","r",stdin);

	int n,m,x,y;
	cin>>n>>m;

	for(int i=0;i<m;++i){
		scanf("%d%d",&a[i],&b[i]);
		adj[a[i]].push_back(i);
		adj[b[i]].push_back(i);
	}
	for(int i=1;i<=n;++i)if(!vis[i])dfs(i);

	int numodd= 0;
	for(int i=0;i<m;++i){
		if(!used[i]){
			x= a[i],y = b[i];
			if(depth[x]<depth[y])swap(x,y);

			if(depth[x]%2 != depth[y]%2){
				++dp2[x],--dp2[y];
			}
			else{
				++dp[x],--dp[y];
				++numodd;
			}
		}
	}

	int ret=0;

	if(numodd==1)++ret;

	while(!st.empty()){
		int u = st.top();
		int p = parent[u];
		st.pop();
		if(dp[u]==numodd && parent[u] && dp2[u]==0){
			++ret;
		}
		dp[p]+=dp[u];
		dp2[p]+=dp2[u];
	}
	cout<<ret<<endl;
}

Compilation message

voltage.cpp: In function 'void dfs(int)':
voltage.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[root].size();++i){
               ^
voltage.cpp: In function 'int main()':
voltage.cpp:42:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a[i],&b[i]);
                            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 3 ms 2856 KB Output is correct
4 Correct 3 ms 2872 KB Output is correct
5 Correct 4 ms 2872 KB Output is correct
6 Correct 4 ms 3000 KB Output is correct
7 Correct 4 ms 3056 KB Output is correct
8 Correct 5 ms 3056 KB Output is correct
9 Correct 4 ms 3056 KB Output is correct
10 Correct 4 ms 3056 KB Output is correct
11 Correct 4 ms 3100 KB Output is correct
12 Correct 4 ms 3128 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 8768 KB Output is correct
2 Correct 99 ms 12820 KB Output is correct
3 Correct 49 ms 12820 KB Output is correct
4 Correct 88 ms 14028 KB Output is correct
5 Correct 14 ms 14028 KB Output is correct
6 Correct 102 ms 14028 KB Output is correct
7 Correct 92 ms 17820 KB Output is correct
8 Correct 90 ms 18912 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 18912 KB Output is correct
2 Correct 46 ms 18988 KB Output is correct
3 Correct 48 ms 18988 KB Output is correct
4 Correct 3 ms 18988 KB Output is correct
5 Correct 62 ms 18988 KB Output is correct
6 Correct 74 ms 18988 KB Output is correct
7 Correct 96 ms 18988 KB Output is correct
8 Correct 81 ms 20480 KB Output is correct
9 Correct 84 ms 21376 KB Output is correct
10 Correct 87 ms 21376 KB Output is correct
11 Correct 70 ms 21376 KB Output is correct
12 Correct 81 ms 22444 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 22444 KB Output is correct
2 Correct 74 ms 27988 KB Output is correct
3 Correct 5 ms 27988 KB Output is correct
4 Correct 96 ms 27988 KB Output is correct
5 Correct 112 ms 27988 KB Output is correct
6 Correct 102 ms 27988 KB Output is correct
7 Correct 155 ms 30464 KB Output is correct
8 Correct 174 ms 33268 KB Output is correct
9 Correct 148 ms 33816 KB Output is correct
10 Correct 163 ms 38616 KB Output is correct
11 Correct 132 ms 38696 KB Output is correct
12 Correct 157 ms 43176 KB Output is correct
13 Correct 117 ms 43176 KB Output is correct
14 Correct 132 ms 48700 KB Output is correct
15 Correct 147 ms 50236 KB Output is correct
16 Correct 140 ms 51712 KB Output is correct
17 Correct 136 ms 52332 KB Output is correct
18 Correct 119 ms 54596 KB Output is correct