# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
49070 | 2018-05-21T18:53:57 Z | yusufake | Duathlon (APIO18_duathlon) | C++ | 176 ms | 30800 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 > U[N],V[N]; ll AP[N],D[N],low[N],T,sz[N],n,m,i,x,y,nn,asd,bcc; stack < int > S; void f(int x, int p){ ll t = sz[x] + U[x].size(); for(auto y : U[x]){ f(y,x); sz[x] += sz[y]; if(x > n) asd -= (t+(p!=-1)) * sz[y] * (sz[y]-1); } if(x > n) asd -= t * (nn-sz[x]) * (nn-sz[x]-1); } void g(int x, int p){ D[x] = low[x] = ++T; nn++; S.push(x); 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]++; U[x].pb(++bcc); for(; S.top() != x ;){ int z = S.top(); S.pop(); if(AP[z]) U[bcc].pb(z); sz[bcc]++; } } } else if(y != p) low[x] = min(low[x] , D[y]); } } int main(){ cin >> n >> m; for(;m--;){ scanf("%d%d",&x,&y); V[x].pb(y); V[y].pb(x); } bcc = n; for(i=1;i<=n;i++) if(!D[i]){ for(;S.size();) S.pop(); nn = 0; g(i,-1); asd += nn * (nn-1) * (nn-2); if(AP[i]) f(i,-1); else{ x = U[i][0]; sz[x]++; f(x,-1); } } cout << asd; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 14456 KB | Output is correct |
2 | Correct | 13 ms | 14456 KB | Output is correct |
3 | Correct | 13 ms | 14488 KB | Output is correct |
4 | Correct | 15 ms | 14488 KB | Output is correct |
5 | Correct | 25 ms | 14488 KB | Output is correct |
6 | Correct | 19 ms | 14488 KB | Output is correct |
7 | Incorrect | 19 ms | 14488 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 14456 KB | Output is correct |
2 | Correct | 13 ms | 14456 KB | Output is correct |
3 | Correct | 13 ms | 14488 KB | Output is correct |
4 | Correct | 15 ms | 14488 KB | Output is correct |
5 | Correct | 25 ms | 14488 KB | Output is correct |
6 | Correct | 19 ms | 14488 KB | Output is correct |
7 | Incorrect | 19 ms | 14488 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 131 ms | 29788 KB | Output is correct |
2 | Correct | 109 ms | 29796 KB | Output is correct |
3 | Incorrect | 176 ms | 30800 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 30800 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 169 ms | 30800 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 19 ms | 30800 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 162 ms | 30800 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 14456 KB | Output is correct |
2 | Correct | 13 ms | 14456 KB | Output is correct |
3 | Correct | 13 ms | 14488 KB | Output is correct |
4 | Correct | 15 ms | 14488 KB | Output is correct |
5 | Correct | 25 ms | 14488 KB | Output is correct |
6 | Correct | 19 ms | 14488 KB | Output is correct |
7 | Incorrect | 19 ms | 14488 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 14456 KB | Output is correct |
2 | Correct | 13 ms | 14456 KB | Output is correct |
3 | Correct | 13 ms | 14488 KB | Output is correct |
4 | Correct | 15 ms | 14488 KB | Output is correct |
5 | Correct | 25 ms | 14488 KB | Output is correct |
6 | Correct | 19 ms | 14488 KB | Output is correct |
7 | Incorrect | 19 ms | 14488 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |