oj.uz

Submission #25763

# Submission time Handle Problem Language Result Execution time Memory
25763 2017-06-24T05:33:17 Z kriii 전압 (JOI14_voltage) C++14
45 / 100
 229 ms 15164 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);
	}

	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;
}

Compilation message

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.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 0 ms 7428 KB Output is correct
8 Incorrect 0 ms 7428 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 11144 KB Output is correct
2 Correct 59 ms 13180 KB Output is correct
3 Correct 36 ms 11144 KB Output is correct
4 Correct 126 ms 14148 KB Output is correct
5 Correct 6 ms 7856 KB Output is correct
6 Correct 116 ms 11988 KB Output is correct
7 Correct 146 ms 15160 KB Output is correct
8 Correct 133 ms 15160 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11144 KB Output is correct
2 Correct 43 ms 15164 KB Output is correct
3 Correct 36 ms 15156 KB Output is correct
4 Correct 0 ms 7428 KB Output is correct
5 Correct 49 ms 12144 KB Output is correct
6 Correct 113 ms 10728 KB Output is correct
7 Correct 136 ms 12584 KB Output is correct
8 Correct 146 ms 13612 KB Output is correct
9 Correct 109 ms 13388 KB Output is correct
10 Correct 133 ms 12388 KB Output is correct
11 Correct 96 ms 10728 KB Output is correct
12 Correct 106 ms 11676 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 12172 KB Output is correct
2 Correct 86 ms 15164 KB Output is correct
3 Correct 3 ms 7428 KB Output is correct
4 Correct 93 ms 13064 KB Output is correct
5 Correct 106 ms 13832 KB Output is correct
6 Correct 109 ms 12944 KB Output is correct
7 Correct 123 ms 13580 KB Output is correct
8 Correct 229 ms 13968 KB Output is correct
9 Correct 209 ms 12612 KB Output is correct
10 Correct 189 ms 14540 KB Output is correct
11 Correct 196 ms 12844 KB Output is correct
12 Correct 213 ms 14560 KB Output is correct
13 Incorrect 169 ms 12876 KB Output isn't correct
14 Halted 0 ms 0 KB -