oj.uz

Submission #48876

# Submission time Handle Problem Language Result Execution time Memory
48876 2018-05-19T11:49:25 Z kriii Duathlon (APIO18_duathlon) C++17
31 / 100
 360 ms 32228 KB 
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;

int N,M,X[200200],Y[200200],P[200200]; bool chk[300300];
vector<int> G[100100],V[300300];
int dep[200200],low[200200];
int sz[300300],ho[300300];

int find(int x)
{
	if (P[x] != x) P[x] = find(P[x]);
	return P[x];
}

void go(int x, int l)
{
	low[x] = dep[x];
	chk[x] = 1;
	for (auto &i : G[x]) if (i != l){
		int y = (x == X[i] ? Y[i] : X[i]);
		if (!chk[y]){
			dep[y] = dep[x] + 1;
			go(y,i);
			if (dep[x] > low[y]){
				if (l != -1) P[find(l)] = find(i);
			}
			if (low[x] > low[y])
				low[x] = low[y];
		}
		else{
			if (l != -1) P[find(l)] = find(i);
			if (low[x] > dep[y]){
				low[x] = dep[y];
			}
		}
	}
}

vector<int> comp;
void gather(int x, int l)
{
	comp.push_back(x);
	chk[x] = 1;
	for (auto &y : V[x]) if (y != l){
		gather(y,x);
	}
}

long long ans;
int bye(int x, int l, int c)
{
	int s = sz[x];
	for (auto &y : V[x]) if (y != l){
		int n = bye(y,x,c);
		if (x >= N) ans -= (long long)n * (n - 1) * (ho[x] - 1);
		else ans -= (long long)(c - n) * (c - n - 1) * (ho[y] - 1);
		s += n;
	}
	return s;
}

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

	for (int i=0;i<N;i++) if (!chk[i]) go(i,-1);

	for (int i=0;i<N;i++){
		set<int> s;
		for (auto &e : G[i]){
			s.insert(find(e));
		}

		if (s.size() == 1) sz[N+*s.begin()]++;
		else{
			sz[i] = 1;
			for (auto &e : s){
				V[i].push_back(N+e);
				V[N+e].push_back(i);
			}
		}
	}
	for (int i=0;i<N+M;i++) chk[i] = 0;

	for (int i=0;i<N+M;i++) if (!chk[i]){
		comp.clear();
		gather(i,-1);
		int C = 0;
		for (auto &x : comp) C += sz[x];
		for (auto &x : comp){
			ho[x] = sz[x];
			for (auto &y : V[x]) ho[x] += sz[y];
		}

		ans += (long long) C * (C - 1) * (C - 2);

		bye(i,-1,C);
	}

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

	return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&N,&M);
  ~~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:68:9: 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 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9784 KB Output is correct
4 Correct 10 ms 9784 KB Output is correct
5 Correct 9 ms 9904 KB Output is correct
6 Correct 12 ms 9904 KB Output is correct
7 Correct 11 ms 9904 KB Output is correct
8 Incorrect 9 ms 9904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9784 KB Output is correct
4 Correct 10 ms 9784 KB Output is correct
5 Correct 9 ms 9904 KB Output is correct
6 Correct 12 ms 9904 KB Output is correct
7 Correct 11 ms 9904 KB Output is correct
8 Incorrect 9 ms 9904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 23824 KB Output is correct
2 Correct 118 ms 23868 KB Output is correct
3 Correct 195 ms 26548 KB Output is correct
4 Correct 210 ms 26548 KB Output is correct
5 Correct 173 ms 26548 KB Output is correct
6 Correct 218 ms 26548 KB Output is correct
7 Correct 215 ms 26548 KB Output is correct
8 Correct 234 ms 26548 KB Output is correct
9 Correct 214 ms 26548 KB Output is correct
10 Correct 262 ms 26548 KB Output is correct
11 Correct 176 ms 26548 KB Output is correct
12 Correct 107 ms 26548 KB Output is correct
13 Correct 99 ms 26548 KB Output is correct
14 Correct 117 ms 26548 KB Output is correct
15 Correct 89 ms 26548 KB Output is correct
16 Correct 90 ms 26548 KB Output is correct
17 Correct 17 ms 26548 KB Output is correct
18 Correct 14 ms 26548 KB Output is correct
19 Correct 14 ms 26548 KB Output is correct
20 Correct 14 ms 26548 KB Output is correct
21 Correct 17 ms 26548 KB Output is correct
22 Correct 14 ms 26548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26548 KB Output is correct
2 Correct 10 ms 26548 KB Output is correct
3 Correct 9 ms 26548 KB Output is correct
4 Correct 12 ms 26548 KB Output is correct
5 Correct 16 ms 26548 KB Output is correct
6 Correct 14 ms 26548 KB Output is correct
7 Correct 13 ms 26548 KB Output is correct
8 Correct 14 ms 26548 KB Output is correct
9 Correct 10 ms 26548 KB Output is correct
10 Correct 12 ms 26548 KB Output is correct
11 Correct 13 ms 26548 KB Output is correct
12 Correct 12 ms 26548 KB Output is correct
13 Correct 10 ms 26548 KB Output is correct
14 Correct 10 ms 26548 KB Output is correct
15 Correct 13 ms 26548 KB Output is correct
16 Correct 11 ms 26548 KB Output is correct
17 Correct 12 ms 26548 KB Output is correct
18 Correct 13 ms 26548 KB Output is correct
19 Correct 14 ms 26548 KB Output is correct
20 Correct 11 ms 26548 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 26548 KB Output is correct
2 Correct 272 ms 26548 KB Output is correct
3 Correct 225 ms 26548 KB Output is correct
4 Correct 249 ms 26548 KB Output is correct
5 Correct 252 ms 26548 KB Output is correct
6 Correct 360 ms 32228 KB Output is correct
7 Correct 338 ms 32228 KB Output is correct
8 Correct 337 ms 32228 KB Output is correct
9 Correct 344 ms 32228 KB Output is correct
10 Correct 263 ms 32228 KB Output is correct
11 Correct 285 ms 32228 KB Output is correct
12 Correct 214 ms 32228 KB Output is correct
13 Correct 242 ms 32228 KB Output is correct
14 Correct 148 ms 32228 KB Output is correct
15 Correct 176 ms 32228 KB Output is correct
16 Correct 77 ms 32228 KB Output is correct
17 Correct 143 ms 32228 KB Output is correct
18 Correct 135 ms 32228 KB Output is correct
19 Correct 140 ms 32228 KB Output is correct
20 Correct 148 ms 32228 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32228 KB Output is correct
2 Correct 10 ms 32228 KB Output is correct
3 Incorrect 10 ms 32228 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 32228 KB Output is correct
2 Correct 274 ms 32228 KB Output is correct
3 Incorrect 268 ms 32228 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9784 KB Output is correct
4 Correct 10 ms 9784 KB Output is correct
5 Correct 9 ms 9904 KB Output is correct
6 Correct 12 ms 9904 KB Output is correct
7 Correct 11 ms 9904 KB Output is correct
8 Incorrect 9 ms 9904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9784 KB Output is correct
4 Correct 10 ms 9784 KB Output is correct
5 Correct 9 ms 9904 KB Output is correct
6 Correct 12 ms 9904 KB Output is correct
7 Correct 11 ms 9904 KB Output is correct
8 Incorrect 9 ms 9904 KB Output isn't correct
9 Halted 0 ms 0 KB -