oj.uz

Submission #43328

# Submission time Handle Problem Language Result Execution time Memory
43328 2018-03-13T16:28:27 Z ffresh 전압 (JOI14_voltage) C++14
0 / 100
 100 ms 25480 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]){

				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(p==0)continue;

		if(dp[u]==numodd && 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:24: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:45: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
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 4 ms 2888 KB Output is correct
4 Correct 4 ms 2928 KB Output is correct
5 Correct 4 ms 3064 KB Output is correct
6 Correct 4 ms 3064 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Incorrect 4 ms 3208 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 9040 KB Output is correct
2 Correct 95 ms 14188 KB Output is correct
3 Correct 53 ms 14188 KB Output is correct
4 Incorrect 100 ms 17852 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17852 KB Output is correct
2 Correct 49 ms 20308 KB Output is correct
3 Correct 49 ms 21368 KB Output is correct
4 Correct 3 ms 21368 KB Output is correct
5 Incorrect 64 ms 21368 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 21368 KB Output is correct
2 Correct 77 ms 25480 KB Output is correct
3 Correct 5 ms 25480 KB Output is correct
4 Incorrect 96 ms 25480 KB Output isn't correct
5 Halted 0 ms 0 KB -