oj.uz

Submission #48978

# Submission time Handle Problem Language Result Execution time Memory
48978 2018-05-21T02:50:25 Z yusufake Duathlon (APIO18_duathlon) C++
31 / 100
 188 ms 17908 KB 
#include<bits/stdc++.h> 
using namespace std; 

#define pb push_back
typedef long long ll; 
typedef pair < int , int > pp; 
const int mod = 1e9 + 7; 
const int N   = 2e5 + 5; 

vector < int > V[N]; 

ll AP[N],D[N],low[N],T,low2[N],D2[N],sz[N],n,m,i,x,y,nn,asd;
stack < int > S; 

void f(int x, int p){
    D2[x] = low2[x] = ++T;
    sz[x] = 1;
	S.push(x);
	for(auto y : V[x]){
		if(!D2[y]){
			f(y,x);
            low2[x] = min(low2[x] , low2[y]);
			sz[x] += sz[y];
			if(low2[y] >= D2[x]){
				ll t=0,a=0;
				for(; S.top() != x ;){
					int z = S.top();
					S.pop();
					if(AP[z]) t += sz[z] * (sz[z]-1);
					a++;
				}
				asd -= a * t;
				asd -= a * (nn-sz[y]) * (nn-sz[y]-1);
			}
		}
        else if(y != p) low2[x] = min(low2[x] , D2[y]);
    }	
}

int ap;
void g(int x, int p){
    D[x] = low[x] = ++T; nn++;
	AP[x] = p == -1 ? -1 : 0;
	for(auto y : V[x]){
		if(!D[y]){
			g(y,x);
			low[x] = min(low[x] , low[y]);
			if(low[y] >= D[x]) AP[x]++;
        }
		else if(y != p) low[x] = min(low[x] , D[y]);
	}	
    if(AP[x]) ap=x;
}
int main(){
  cin >> n >> m;
  for(;m--;){
  	scanf("%d%d",&x,&y);
  	V[x].pb(y); V[y].pb(x);
  }
  
  for(i=1;i<=n;i++)
  	if(!D[i]){
  		nn = ap = 0; g(i,-1);
  		asd += nn * (nn-1) * (nn-2);
        for(;S.size();) S.pop();
  		if(ap) f(ap,-1);
  	}
    
    cout << asd;
    return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:57:22: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
    scanf("%d%d",&x,&y);
                 ~~   ^
count_triplets.cpp:57:22: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
count_triplets.cpp:57:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&x,&y);
    ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5092 KB Output is correct
3 Correct 5 ms 5168 KB Output is correct
4 Correct 5 ms 5244 KB Output is correct
5 Correct 5 ms 5244 KB Output is correct
6 Correct 5 ms 5320 KB Output is correct
7 Incorrect 5 ms 5320 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5092 KB Output is correct
3 Correct 5 ms 5168 KB Output is correct
4 Correct 5 ms 5244 KB Output is correct
5 Correct 5 ms 5244 KB Output is correct
6 Correct 5 ms 5320 KB Output is correct
7 Incorrect 5 ms 5320 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 91 ms 16924 KB Output is correct
2 Correct 119 ms 16996 KB Output is correct
3 Correct 103 ms 16996 KB Output is correct
4 Correct 164 ms 17908 KB Output is correct
5 Correct 121 ms 17908 KB Output is correct
6 Correct 128 ms 17908 KB Output is correct
7 Correct 188 ms 17908 KB Output is correct
8 Correct 151 ms 17908 KB Output is correct
9 Correct 135 ms 17908 KB Output is correct
10 Correct 145 ms 17908 KB Output is correct
11 Correct 129 ms 17908 KB Output is correct
12 Correct 87 ms 17908 KB Output is correct
13 Correct 73 ms 17908 KB Output is correct
14 Correct 95 ms 17908 KB Output is correct
15 Correct 71 ms 17908 KB Output is correct
16 Correct 64 ms 17908 KB Output is correct
17 Correct 12 ms 17908 KB Output is correct
18 Correct 11 ms 17908 KB Output is correct
19 Correct 12 ms 17908 KB Output is correct
20 Correct 13 ms 17908 KB Output is correct
21 Correct 17 ms 17908 KB Output is correct
22 Correct 13 ms 17908 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 17908 KB Output is correct
2 Correct 102 ms 17908 KB Output is correct
3 Correct 103 ms 17908 KB Output is correct
4 Correct 102 ms 17908 KB Output is correct
5 Correct 110 ms 17908 KB Output is correct
6 Correct 125 ms 17908 KB Output is correct
7 Correct 129 ms 17908 KB Output is correct
8 Correct 128 ms 17908 KB Output is correct
9 Correct 142 ms 17908 KB Output is correct
10 Correct 150 ms 17908 KB Output is correct
11 Correct 115 ms 17908 KB Output is correct
12 Correct 128 ms 17908 KB Output is correct
13 Correct 113 ms 17908 KB Output is correct
14 Correct 139 ms 17908 KB Output is correct
15 Correct 125 ms 17908 KB Output is correct
16 Correct 47 ms 17908 KB Output is correct
17 Correct 73 ms 17908 KB Output is correct
18 Correct 61 ms 17908 KB Output is correct
19 Correct 71 ms 17908 KB Output is correct
20 Correct 63 ms 17908 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5092 KB Output is correct
3 Correct 5 ms 5168 KB Output is correct
4 Correct 5 ms 5244 KB Output is correct
5 Correct 5 ms 5244 KB Output is correct
6 Correct 5 ms 5320 KB Output is correct
7 Incorrect 5 ms 5320 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5092 KB Output is correct
3 Correct 5 ms 5168 KB Output is correct
4 Correct 5 ms 5244 KB Output is correct
5 Correct 5 ms 5244 KB Output is correct
6 Correct 5 ms 5320 KB Output is correct
7 Incorrect 5 ms 5320 KB Output isn't correct
8 Halted 0 ms 0 KB -