oj.uz

Submission #912743

# Submission time Handle Problem Language Result Execution time Memory
912743 2024-01-19T19:34:47 Z imarn Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048576 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
using namespace std;
const int N=1e5+5;
vi g[N];stack<int>st;
vvi cmp,bst;
unsigned ll d[N]{0},lo[N]{0},t=0,ap[N]{0},id[N]{0},cur=0,isap[N]{0},sz[N],dp[N];
void dfs(int u,int p,int gr){
    lo[u]=gr;d[u]=1;
    for(auto v:g[u]){
        if(v==p)continue;
        dfs(v,u,gr);d[u]+=d[v];
    }
}
ll ans=0,n;
void solve(int u,int p){
    dp[u]=1;id[u]=1;
    ll tt=0;
    for(auto v:g[u]){
        if(v==p)continue;
        solve(v,u);
        if(isap[u])ans+=2*(dp[u]-1)*(dp[v]);
        dp[u]+=dp[v];
    }
    if(isap[u])ans+=2*(d[lo[u]]-dp[u])*(dp[u]-1);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        g[u].pb(v);g[v].pb(u);
    }
    //dfs(1,1);build(n);
    for(int i=1;i<=n;i++)if(!d[i])dfs(i,i,i);
    for(int i=1;i<=n;i++)sz[i]=1,isap[i]=1;
    for(int i=1;i<=n;i++)if(!id[i])solve(i,i);cout<<ans;
}

Compilation message

count_triplets.cpp: In function 'void solve(int, int)':
count_triplets.cpp:27:8: warning: unused variable 'tt' [-Wunused-variable]
   27 |     ll tt=0;
      |        ^~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:46:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   46 |     for(int i=1;i<=n;i++)if(!id[i])solve(i,i);cout<<ans;
      |     ^~~
count_triplets.cpp:46:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   46 |     for(int i=1;i<=n;i++)if(!id[i])solve(i,i);cout<<ans;
      |                                               ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 664 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 664 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1131 ms 969676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8040 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 3 ms 8036 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 3 ms 8040 KB Output is correct
7 Correct 3 ms 8028 KB Output is correct
8 Correct 3 ms 8168 KB Output is correct
9 Correct 2 ms 8036 KB Output is correct
10 Correct 3 ms 8028 KB Output is correct
11 Correct 3 ms 8032 KB Output is correct
12 Correct 2 ms 8108 KB Output is correct
13 Correct 3 ms 8024 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8044 KB Output is correct
16 Correct 2 ms 8032 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 3 ms 8152 KB Output is correct
19 Correct 3 ms 8028 KB Output is correct
20 Correct 2 ms 8036 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 11348 KB Output is correct
2 Correct 30 ms 11608 KB Output is correct
3 Correct 31 ms 11356 KB Output is correct
4 Correct 47 ms 11360 KB Output is correct
5 Correct 31 ms 11364 KB Output is correct
6 Correct 42 ms 15440 KB Output is correct
7 Correct 41 ms 14164 KB Output is correct
8 Correct 64 ms 13648 KB Output is correct
9 Correct 34 ms 12628 KB Output is correct
10 Correct 41 ms 11356 KB Output is correct
11 Correct 43 ms 12588 KB Output is correct
12 Correct 33 ms 12720 KB Output is correct
13 Correct 31 ms 12624 KB Output is correct
14 Correct 39 ms 12368 KB Output is correct
15 Correct 39 ms 12304 KB Output is correct
16 Correct 18 ms 11104 KB Output is correct
17 Correct 25 ms 13008 KB Output is correct
18 Correct 30 ms 12880 KB Output is correct
19 Correct 28 ms 13008 KB Output is correct
20 Correct 28 ms 12900 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8040 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Runtime error 734 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11368 KB Output is correct
2 Correct 32 ms 11360 KB Output is correct
3 Runtime error 805 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 664 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 664 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -