oj.uz

Submission #48979

# Submission time Handle Problem Language Result Execution time Memory
48979 2018-05-21T02:59:15 Z yusufake Duathlon (APIO18_duathlon) C++
31 / 100
 194 ms 20892 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   = 3e5 + 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,ss=0;
				for(; S.top() != x ;){
					int z = S.top();
					S.pop();
					if(AP[z]) { ss += sz[z]-1; t += sz[z] * (sz[z]-1); }
					a++;
                    ss++;
				}
				asd -= a * t;
				asd -= a * (nn-ss) * (nn-ss-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:58: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:58:22: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
count_triplets.cpp:58: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 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 11 ms 7564 KB Output is correct
4 Correct 8 ms 7564 KB Output is correct
5 Correct 7 ms 7584 KB Output is correct
6 Correct 7 ms 7584 KB Output is correct
7 Incorrect 8 ms 7600 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 11 ms 7564 KB Output is correct
4 Correct 8 ms 7564 KB Output is correct
5 Correct 7 ms 7584 KB Output is correct
6 Correct 7 ms 7584 KB Output is correct
7 Incorrect 8 ms 7600 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 129 ms 19408 KB Output is correct
2 Correct 126 ms 19408 KB Output is correct
3 Correct 133 ms 19552 KB Output is correct
4 Correct 129 ms 20296 KB Output is correct
5 Correct 99 ms 20296 KB Output is correct
6 Correct 144 ms 20296 KB Output is correct
7 Correct 101 ms 20296 KB Output is correct
8 Correct 108 ms 20296 KB Output is correct
9 Correct 110 ms 20296 KB Output is correct
10 Correct 111 ms 20296 KB Output is correct
11 Correct 119 ms 20296 KB Output is correct
12 Correct 88 ms 20296 KB Output is correct
13 Correct 89 ms 20296 KB Output is correct
14 Correct 102 ms 20296 KB Output is correct
15 Correct 74 ms 20296 KB Output is correct
16 Correct 99 ms 20296 KB Output is correct
17 Correct 21 ms 20296 KB Output is correct
18 Correct 18 ms 20296 KB Output is correct
19 Correct 20 ms 20296 KB Output is correct
20 Correct 16 ms 20296 KB Output is correct
21 Correct 18 ms 20296 KB Output is correct
22 Correct 16 ms 20296 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 20296 KB Output is correct
2 Correct 132 ms 20296 KB Output is correct
3 Correct 83 ms 20296 KB Output is correct
4 Correct 192 ms 20296 KB Output is correct
5 Correct 190 ms 20296 KB Output is correct
6 Correct 194 ms 20892 KB Output is correct
7 Correct 145 ms 20892 KB Output is correct
8 Correct 168 ms 20892 KB Output is correct
9 Correct 160 ms 20892 KB Output is correct
10 Correct 156 ms 20892 KB Output is correct
11 Correct 157 ms 20892 KB Output is correct
12 Correct 145 ms 20892 KB Output is correct
13 Correct 162 ms 20892 KB Output is correct
14 Correct 115 ms 20892 KB Output is correct
15 Correct 99 ms 20892 KB Output is correct
16 Correct 78 ms 20892 KB Output is correct
17 Correct 82 ms 20892 KB Output is correct
18 Correct 80 ms 20892 KB Output is correct
19 Correct 90 ms 20892 KB Output is correct
20 Correct 87 ms 20892 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 11 ms 7564 KB Output is correct
4 Correct 8 ms 7564 KB Output is correct
5 Correct 7 ms 7584 KB Output is correct
6 Correct 7 ms 7584 KB Output is correct
7 Incorrect 8 ms 7600 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 11 ms 7564 KB Output is correct
4 Correct 8 ms 7564 KB Output is correct
5 Correct 7 ms 7584 KB Output is correct
6 Correct 7 ms 7584 KB Output is correct
7 Incorrect 8 ms 7600 KB Output isn't correct
8 Halted 0 ms 0 KB -