제출 #43352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43352		ffresh	전압 (JOI14_voltage)	C++14	100 / 100	174 ms	54596 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]%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;
}

컴파일 시 표준 에러 (stderr) 메시지

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