Submission #25767

#	Time	Username	Problem	Language	Result	Execution time	Memory
25767		kriii	전압 (JOI14_voltage)	C++14	100 / 100	229 ms	15160 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);
	}

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

		int r = 0;
		if (badback == 0) r += bridge;
		else if (badback == 1) r++;

		if (badback >= 1){
			if (badmx == badback) r += badmxcnt;
		}
		res.push_back(r);
		bad.push_back(badback >= 1);
	}

	int ans = 0;
	int bads = 0;
	for (int x : bad) bads += x;

	if (bads == 0){
		for (int x : res) ans += x;
	}
	else if (bads == 1){
		for (int i=0;i<bad.size();i++) if (bad[i]) ans += res[i];
	}
	printf ("%d\n",ans);

	return 0;
}

Compilation message (stderr)

voltage.cpp: In function 'int main()':
voltage.cpp:84:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0;i<bad.size();i++) if (bad[i]) ans += res[i];
                 ^
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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45