oj.uz

Submission #218272

# Submission time Handle Problem Language Result Execution time Memory
218272 2020-04-01T18:52:53 Z VEGAnn Duathlon (APIO18_duathlon) C++14
31 / 100
 232 ms 34668 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 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 12 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 12 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 104 ms 24568 KB Output is correct
2 Correct 110 ms 24668 KB Output is correct
3 Correct 162 ms 28528 KB Output is correct
4 Correct 127 ms 24952 KB Output is correct
5 Correct 145 ms 24688 KB Output is correct
6 Correct 177 ms 27632 KB Output is correct
7 Correct 169 ms 24948 KB Output is correct
8 Correct 169 ms 25584 KB Output is correct
9 Correct 161 ms 23160 KB Output is correct
10 Correct 151 ms 23268 KB Output is correct
11 Correct 104 ms 19064 KB Output is correct
12 Correct 105 ms 19064 KB Output is correct
13 Correct 90 ms 18424 KB Output is correct
14 Correct 104 ms 18416 KB Output is correct
15 Correct 64 ms 16760 KB Output is correct
16 Correct 65 ms 16760 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 11776 KB Output is correct
20 Correct 14 ms 11648 KB Output is correct
21 Correct 14 ms 11648 KB Output is correct
22 Correct 16 ms 11648 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 11 ms 9984 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 11 ms 10112 KB Output is correct
5 Correct 11 ms 9984 KB Output is correct
6 Correct 11 ms 9984 KB Output is correct
7 Correct 11 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 13 ms 10112 KB Output is correct
11 Correct 11 ms 9856 KB Output is correct
12 Correct 11 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 10 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 12 ms 9984 KB Output is correct
20 Correct 11 ms 9856 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 23152 KB Output is correct
2 Correct 166 ms 23280 KB Output is correct
3 Correct 184 ms 23408 KB Output is correct
4 Correct 171 ms 23280 KB Output is correct
5 Correct 169 ms 23280 KB Output is correct
6 Correct 232 ms 34668 KB Output is correct
7 Correct 211 ms 30824 KB Output is correct
8 Correct 208 ms 30060 KB Output is correct
9 Correct 197 ms 27884 KB Output is correct
10 Correct 173 ms 23156 KB Output is correct
11 Correct 165 ms 23152 KB Output is correct
12 Correct 172 ms 22904 KB Output is correct
13 Correct 164 ms 22904 KB Output is correct
14 Correct 137 ms 21752 KB Output is correct
15 Correct 114 ms 20728 KB Output is correct
16 Correct 65 ms 17400 KB Output is correct
17 Correct 105 ms 25840 KB Output is correct
18 Correct 97 ms 23536 KB Output is correct
19 Correct 91 ms 22868 KB Output is correct
20 Correct 89 ms 22496 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 185 ms 23212 KB Output is correct
2 Correct 179 ms 23536 KB Output is correct
3 Incorrect 190 ms 23148 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 12 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 12 ms 9728 KB Output isn't correct
8 Halted 0 ms 0 KB -