Submission #43328

#	Time	Username	Problem	Language	Result	Execution time	Memory
43328		ffresh	전압 (JOI14_voltage)	C++14	0 / 100	100 ms	25480 KiB

voltage

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 35
• Subtask 4: 0 / 45