oj.uz

Submission #218501

# Submission time Handle Problem Language Result Execution time Memory
218501 2020-04-02T08:29:58 Z VEGAnn Duathlon (APIO18_duathlon) C++14
31 / 100
 258 ms 33132 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 10 ms 9728 KB Output is correct
2 Correct 10 ms 9800 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 13 ms 9728 KB Output is correct
6 Correct 13 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Incorrect 10 ms 9780 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9800 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 13 ms 9728 KB Output is correct
6 Correct 13 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Incorrect 10 ms 9780 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 119 ms 24952 KB Output is correct
2 Correct 115 ms 24824 KB Output is correct
3 Correct 200 ms 27560 KB Output is correct
4 Correct 135 ms 25244 KB Output is correct
5 Correct 178 ms 24088 KB Output is correct
6 Correct 231 ms 26760 KB Output is correct
7 Correct 206 ms 24528 KB Output is correct
8 Correct 192 ms 25068 KB Output is correct
9 Correct 184 ms 23032 KB Output is correct
10 Correct 195 ms 23076 KB Output is correct
11 Correct 103 ms 19196 KB Output is correct
12 Correct 109 ms 19064 KB Output is correct
13 Correct 89 ms 18424 KB Output is correct
14 Correct 100 ms 18424 KB Output is correct
15 Correct 64 ms 16680 KB Output is correct
16 Correct 63 ms 16632 KB Output is correct
17 Correct 14 ms 11264 KB Output is correct
18 Correct 15 ms 11392 KB Output is correct
19 Correct 14 ms 11264 KB Output is correct
20 Correct 14 ms 11264 KB Output is correct
21 Correct 14 ms 11264 KB Output is correct
22 Correct 14 ms 11264 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 23616 KB Output is correct
2 Correct 207 ms 23536 KB Output is correct
3 Correct 164 ms 23536 KB Output is correct
4 Correct 181 ms 23616 KB Output is correct
5 Correct 163 ms 23536 KB Output is correct
6 Correct 258 ms 33132 KB Output is correct
7 Correct 247 ms 29792 KB Output is correct
8 Correct 209 ms 29292 KB Output is correct
9 Correct 191 ms 27372 KB Output is correct
10 Correct 167 ms 23284 KB Output is correct
11 Correct 168 ms 23408 KB Output is correct
12 Correct 164 ms 23160 KB Output is correct
13 Correct 158 ms 23160 KB Output is correct
14 Correct 133 ms 22084 KB Output is correct
15 Correct 110 ms 20856 KB Output is correct
16 Correct 63 ms 17144 KB Output is correct
17 Correct 94 ms 26096 KB Output is correct
18 Correct 98 ms 23824 KB Output is correct
19 Correct 95 ms 23020 KB Output is correct
20 Correct 95 ms 22776 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 23660 KB Output is correct
2 Correct 174 ms 23792 KB Output is correct
3 Incorrect 175 ms 22512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9800 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 13 ms 9728 KB Output is correct
6 Correct 13 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Incorrect 10 ms 9780 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9800 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 13 ms 9728 KB Output is correct
6 Correct 13 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Incorrect 10 ms 9780 KB Output isn't correct
9 Halted 0 ms 0 KB -