oj.uz

Submission #218273

# Submission time Handle Problem Language Result Execution time Memory
218273 2020-04-01T19:21:57 Z VEGAnn Duathlon (APIO18_duathlon) C++14
31 / 100
 242 ms 34408 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

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

    ll sum = 0ll;

    for (int u : V[v]){

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

        if (v >= N){
            if (u != p){
                ll cur = c - siz[u] - sz[v];

                ans += (cur * ll(sz[v]));
            } else {
                ll cur = siz[v] - sz[v];

                ans += (cur * ll(sz[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:97: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:99: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 11 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 11 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 102 ms 24444 KB Output is correct
2 Correct 104 ms 24440 KB Output is correct
3 Correct 166 ms 28272 KB Output is correct
4 Correct 130 ms 24696 KB Output is correct
5 Correct 151 ms 24560 KB Output is correct
6 Correct 180 ms 27248 KB Output is correct
7 Correct 176 ms 24692 KB Output is correct
8 Correct 177 ms 25328 KB Output is correct
9 Correct 188 ms 22904 KB Output is correct
10 Correct 170 ms 23028 KB Output is correct
11 Correct 112 ms 18936 KB Output is correct
12 Correct 117 ms 18848 KB Output is correct
13 Correct 108 ms 18168 KB Output is correct
14 Correct 96 ms 18168 KB Output is correct
15 Correct 65 ms 16508 KB Output is correct
16 Correct 65 ms 16504 KB Output is correct
17 Correct 14 ms 11776 KB Output is correct
18 Correct 14 ms 11776 KB Output is correct
19 Correct 16 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 14 ms 9856 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 11 ms 10112 KB Output is correct
5 Correct 10 ms 9984 KB Output is correct
6 Correct 10 ms 9984 KB Output is correct
7 Correct 11 ms 9984 KB Output is correct
8 Correct 10 ms 9984 KB Output is correct
9 Correct 10 ms 9984 KB Output is correct
10 Correct 10 ms 9856 KB Output is correct
11 Correct 11 ms 9856 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 10 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 12 ms 9856 KB Output is correct
19 Correct 10 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 167 ms 23024 KB Output is correct
2 Correct 167 ms 23024 KB Output is correct
3 Correct 187 ms 23156 KB Output is correct
4 Correct 167 ms 23024 KB Output is correct
5 Correct 166 ms 23024 KB Output is correct
6 Correct 242 ms 34408 KB Output is correct
7 Correct 209 ms 30572 KB Output is correct
8 Correct 202 ms 29804 KB Output is correct
9 Correct 199 ms 27624 KB Output is correct
10 Correct 166 ms 22772 KB Output is correct
11 Correct 165 ms 22896 KB Output is correct
12 Correct 168 ms 22648 KB Output is correct
13 Correct 173 ms 22816 KB Output is correct
14 Correct 136 ms 21496 KB Output is correct
15 Correct 113 ms 20472 KB Output is correct
16 Correct 63 ms 17144 KB Output is correct
17 Correct 92 ms 25584 KB Output is correct
18 Correct 101 ms 23456 KB Output is correct
19 Correct 96 ms 22604 KB Output is correct
20 Correct 89 ms 22264 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 23064 KB Output is correct
2 Correct 186 ms 23280 KB Output is correct
3 Incorrect 198 ms 22892 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 11 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 11 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 -