oj.uz

Submission #217817

# Submission time Handle Problem Language Result Execution time Memory
217817 2020-03-30T20:45:43 Z VEGAnn Duathlon (APIO18_duathlon) C++14
31 / 100
 229 ms 32748 KB 
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;

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], siz[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 (dep[x] > dep[y]){
			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;
	siz[x] = sz[x];
	for (auto &y : V[x]) if (y != l){
		gather(y,x);
		siz[x] += siz[y];
	}
}

long long ans;
void bye(int v, int p, int c){
    ans += ll(sz[v]) * (ll(sz[v]) - 1ll) * (ll(sz[v]) - 2ll) / 2ll; // first

    if (sz[v])
        ans += (c - ll(sz[v])) * (ll(sz[v]) - 1ll) * (ll(sz[v]));

    ll sum = 0ll;

    for (int u : V[v]){

        if (u != p) {
            bye(u, v, c);
            ans += sum * ll(siz[u]) * ll(sz[v]);
            sum += ll(siz[u]);
        } else {
            ans += sum * (c - ll(siz[v])) * ll(sz[v]);
            sum += (c - ll(siz[v]));
        }

        ans += ll(sz[v]) * (ll(sz[v]) - 1) * ll(sz[u]) / 2ll; //new

    }
}

int main(){

//    freopen("in.txt","r",stdin);

	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 * 2);

	return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:83: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:85: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 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Incorrect 10 ms 9728 KB Output isn't correct
8 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 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Incorrect 10 ms 9728 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 24440 KB Output is correct
2 Correct 98 ms 25592 KB Output is correct
3 Correct 167 ms 28268 KB Output is correct
4 Correct 129 ms 25976 KB Output is correct
5 Correct 143 ms 24816 KB Output is correct
6 Correct 172 ms 27452 KB Output is correct
7 Correct 171 ms 25332 KB Output is correct
8 Correct 182 ms 26096 KB Output is correct
9 Correct 164 ms 23928 KB Output is correct
10 Correct 158 ms 23796 KB Output is correct
11 Correct 105 ms 19960 KB Output is correct
12 Correct 111 ms 19884 KB Output is correct
13 Correct 105 ms 19068 KB Output is correct
14 Correct 89 ms 19064 KB Output is correct
15 Correct 62 ms 17272 KB Output is correct
16 Correct 63 ms 17228 KB Output is correct
17 Correct 14 ms 11776 KB Output is correct
18 Correct 14 ms 11776 KB Output is correct
19 Correct 14 ms 11648 KB Output is correct
20 Correct 15 ms 11776 KB Output is correct
21 Correct 14 ms 11648 KB Output is correct
22 Correct 14 ms 11648 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9856 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 10 ms 9984 KB Output is correct
6 Correct 11 ms 9984 KB Output is correct
7 Correct 14 ms 9984 KB Output is correct
8 Correct 11 ms 9984 KB Output is correct
9 Correct 10 ms 9856 KB Output is correct
10 Correct 11 ms 9856 KB Output is correct
11 Correct 11 ms 9856 KB Output is correct
12 Correct 13 ms 9856 KB Output is correct
13 Correct 10 ms 9856 KB Output is correct
14 Correct 11 ms 9856 KB Output is correct
15 Correct 10 ms 9856 KB Output is correct
16 Correct 10 ms 9856 KB Output is correct
17 Correct 10 ms 9856 KB Output is correct
18 Correct 10 ms 9856 KB Output is correct
19 Correct 11 ms 9856 KB Output is correct
20 Correct 12 ms 9856 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 23300 KB Output is correct
2 Correct 169 ms 23024 KB Output is correct
3 Correct 167 ms 23024 KB Output is correct
4 Correct 175 ms 23024 KB Output is correct
5 Correct 185 ms 23024 KB Output is correct
6 Correct 229 ms 32748 KB Output is correct
7 Correct 206 ms 29420 KB Output is correct
8 Correct 201 ms 28776 KB Output is correct
9 Correct 193 ms 26860 KB Output is correct
10 Correct 167 ms 22772 KB Output is correct
11 Correct 181 ms 23036 KB Output is correct
12 Correct 161 ms 22648 KB Output is correct
13 Correct 161 ms 22648 KB Output is correct
14 Correct 132 ms 21496 KB Output is correct
15 Correct 120 ms 20472 KB Output is correct
16 Correct 69 ms 17144 KB Output is correct
17 Correct 93 ms 25584 KB Output is correct
18 Correct 90 ms 23284 KB Output is correct
19 Correct 90 ms 22636 KB Output is correct
20 Correct 93 ms 22264 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9856 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Incorrect 10 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 171 ms 23024 KB Output is correct
2 Correct 187 ms 23280 KB Output is correct
3 Incorrect 194 ms 22844 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 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Incorrect 10 ms 9728 KB Output isn't correct
8 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 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Incorrect 10 ms 9728 KB Output isn't correct
8 Halted 0 ms 0 KB -