제출 #25763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25763		kriii	전압 (JOI14_voltage)	C++14	45 / 100	229 ms	15164 KiB

voltage

#include <stdio.h>
#include <vector>
using namespace std;

vector<int> G[100100];
int N,M,X[200200],Y[200200],C[200200];
int D[100100],U[100100];

int gety(int x, int i)
{
	return X[i] == x ? Y[i] : X[i];
}

int bridge, badback, badmx, badmxcnt, badcnt[100100], goodcnt[100100];

void dfs(int x)
{
	U[x] = D[x];
	for (auto &i : G[x]) if (!C[i]){
		C[i] = 1;

		int y = gety(x,i);
		if (D[y] == 0){
			D[y] = D[x] + 1;
			dfs(y);
			badcnt[x] += badcnt[y];
			goodcnt[x] += goodcnt[y];
			if (U[y] == D[y]) bridge++;
			if (U[x] > U[y]) U[x] = U[y];
		}
		else{
			if (D[x] % 2 == D[y] % 2){
				badback++;
				badcnt[x]++; badcnt[y]--;
			}
			else{
				goodcnt[x]++; goodcnt[y]--;
			}
			if (U[x] > D[y]) U[x] = D[y];
		}
	}

	if (goodcnt[x] == 0){
		if (badmx < badcnt[x]) badmx = badcnt[x], badmxcnt = 1;
		else if (badmx == badcnt[x]) badmxcnt++;
	}
}

int main()
{
	scanf ("%d %d",&N,&M);
	for (int i=0;i<M;i++){
		scanf ("%d %d",&X[i],&Y[i]);
		G[X[i]].push_back(i);
		G[Y[i]].push_back(i);
	}

	int ans = 0;

	for (int i=1;i<=N;i++) if (D[i] == 0){
		bridge = badback = 0;
		badmx = badmxcnt = 0;
		D[i] = 1;
		dfs(i);

		if (badback == 0) ans += bridge;
		else if (badback == 1) ans++;

		if (badback >= 1){
			if (badmx == badback) ans += badmxcnt;
		}
	}

	printf ("%d\n",ans);

	return 0;
}

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

voltage.cpp: In function 'int main()':
voltage.cpp:51:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&N,&M);
                       ^
voltage.cpp:53:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d",&X[i],&Y[i]);
                              ^

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 0 / 45