oj.uz

Submission #25767

# Submission time Handle Problem Language Result Execution time Memory
25767 2017-06-24T05:36:01 Z kriii 전압 (JOI14_voltage) C++14
100 / 100
 229 ms 15160 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7428 KB Output is correct
2 Correct 0 ms 7428 KB Output is correct
3 Correct 0 ms 7428 KB Output is correct
4 Correct 0 ms 7428 KB Output is correct
5 Correct 0 ms 7428 KB Output is correct
6 Correct 0 ms 7428 KB Output is correct
7 Correct 3 ms 7428 KB Output is correct
8 Correct 0 ms 7428 KB Output is correct
9 Correct 0 ms 7428 KB Output is correct
10 Correct 0 ms 7428 KB Output is correct
11 Correct 0 ms 7428 KB Output is correct
12 Correct 3 ms 7428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11144 KB Output is correct
2 Correct 86 ms 13176 KB Output is correct
3 Correct 56 ms 11144 KB Output is correct
4 Correct 103 ms 14148 KB Output is correct
5 Correct 3 ms 7852 KB Output is correct
6 Correct 103 ms 11988 KB Output is correct
7 Correct 133 ms 15156 KB Output is correct
8 Correct 149 ms 15160 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 11144 KB Output is correct
2 Correct 36 ms 15160 KB Output is correct
3 Correct 53 ms 15156 KB Output is correct
4 Correct 0 ms 7428 KB Output is correct
5 Correct 99 ms 12136 KB Output is correct
6 Correct 106 ms 10728 KB Output is correct
7 Correct 123 ms 12584 KB Output is correct
8 Correct 116 ms 13608 KB Output is correct
9 Correct 103 ms 13388 KB Output is correct
10 Correct 119 ms 12384 KB Output is correct
11 Correct 136 ms 10728 KB Output is correct
12 Correct 116 ms 11672 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12172 KB Output is correct
2 Correct 83 ms 15160 KB Output is correct
3 Correct 6 ms 8880 KB Output is correct
4 Correct 143 ms 13064 KB Output is correct
5 Correct 99 ms 13836 KB Output is correct
6 Correct 109 ms 12944 KB Output is correct
7 Correct 209 ms 13576 KB Output is correct
8 Correct 166 ms 13972 KB Output is correct
9 Correct 219 ms 12612 KB Output is correct
10 Correct 203 ms 14540 KB Output is correct
11 Correct 226 ms 12844 KB Output is correct
12 Correct 229 ms 14560 KB Output is correct
13 Correct 189 ms 12876 KB Output is correct
14 Correct 223 ms 15044 KB Output is correct
15 Correct 216 ms 14588 KB Output is correct
16 Correct 193 ms 14220 KB Output is correct
17 Correct 193 ms 13276 KB Output is correct
18 Correct 159 ms 13952 KB Output is correct