oj.uz

Submission #402282

# Submission time Handle Problem Language Result Execution time Memory
402282 2021-05-11T14:13:12 Z A_D Duathlon (APIO18_duathlon) C++14
31 / 100
 997 ms 1048580 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;
const int N=1e5+100;
vector<int> g[N];
bool vis[N];
bool c[N];
int dep[N];
int sum[N];
int a[N];
int n,ans,nn;
void dfs2(int u,int p)
{
    vis[u]=1;
    for(auto x:g[u])if(c[x])c[u]=1;
    for(auto x:g[u]){
        if(x==p)continue;
        if(vis[x]){
            c[u]=1;
            continue;
        }

        dep[x]=dep[u]+1;
        dfs2(x,u);
        sum[u]+=sum[x];
        a[u]+=a[x];
    }
    sum[u]+=dep[u];
}
void dfs(int u,int p,int ann)
{
    vis[u]=1;
    ans+=ann-(nn);
    //cout<<u<<" "<<ann<<endl;
    ans+=1;
    for(auto x:g[u]){
        if(x==p)continue;
        dfs(x,u,ann+(nn-a[x])-a[x]);
    }
}
void dfs3(int u,int p)
{
    vis[u]=1;
    for(auto x:g[u]){
        if(vis[x])continue;
        dfs3(x,u);
    }
}
void solve()
{
    int m,ann=0;
    cin>>n>>m;
    //if(m>n-1)assert(0);
    for(int i=1;i<=n;i++)a[i]=1;
    while(m--){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs2(i,i);
        }
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            nn=a[i];
            if(c[i]){
                ans+=nn*(nn-1)*(nn-2);
                dfs3(i,i);
                continue;
            }
//            cout<<nn<<" "<<sum[i]<<endl;
            dfs(i,i,sum[i]);
        }
    }
    cout<<ans<<endl;
}

main()
{
    int t=1;
//    cin>>t;
    while(t--)solve();
}

Compilation message

count_triplets.cpp: In function 'void solve()':
count_triplets.cpp:53:11: warning: unused variable 'ann' [-Wunused-variable]
   53 |     int m,ann=0;
      |           ^~~
count_triplets.cpp: At global scope:
count_triplets.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main()
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Incorrect 2 ms 2764 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Incorrect 2 ms 2764 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 177 ms 17240 KB Output is correct
2 Correct 156 ms 17216 KB Output is correct
3 Correct 185 ms 13304 KB Output is correct
4 Correct 194 ms 15264 KB Output is correct
5 Correct 135 ms 12084 KB Output is correct
6 Correct 137 ms 11936 KB Output is correct
7 Correct 170 ms 11012 KB Output is correct
8 Correct 166 ms 11548 KB Output is correct
9 Correct 159 ms 10236 KB Output is correct
10 Correct 161 ms 10940 KB Output is correct
11 Correct 107 ms 9292 KB Output is correct
12 Correct 145 ms 9136 KB Output is correct
13 Correct 134 ms 9028 KB Output is correct
14 Correct 110 ms 8900 KB Output is correct
15 Correct 81 ms 8336 KB Output is correct
16 Correct 89 ms 8264 KB Output is correct
17 Correct 5 ms 4684 KB Output is correct
18 Correct 5 ms 4812 KB Output is correct
19 Correct 5 ms 4684 KB Output is correct
20 Correct 4 ms 4684 KB Output is correct
21 Correct 4 ms 4572 KB Output is correct
22 Correct 4 ms 4556 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 10056 KB Output is correct
2 Correct 163 ms 10032 KB Output is correct
3 Correct 173 ms 9964 KB Output is correct
4 Correct 165 ms 10072 KB Output is correct
5 Correct 134 ms 9964 KB Output is correct
6 Correct 151 ms 13676 KB Output is correct
7 Correct 158 ms 12796 KB Output is correct
8 Correct 176 ms 11972 KB Output is correct
9 Correct 201 ms 11372 KB Output is correct
10 Correct 156 ms 10108 KB Output is correct
11 Correct 144 ms 10012 KB Output is correct
12 Correct 115 ms 10052 KB Output is correct
13 Correct 150 ms 10120 KB Output is correct
14 Correct 132 ms 9640 KB Output is correct
15 Correct 144 ms 9284 KB Output is correct
16 Correct 81 ms 8004 KB Output is correct
17 Correct 111 ms 10232 KB Output is correct
18 Correct 127 ms 10340 KB Output is correct
19 Correct 125 ms 10252 KB Output is correct
20 Correct 123 ms 10156 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2768 KB Output is correct
2 Correct 3 ms 2764 KB Output is correct
3 Runtime error 721 ms 1048580 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 142 ms 9992 KB Output is correct
2 Correct 178 ms 9896 KB Output is correct
3 Runtime error 997 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Incorrect 2 ms 2764 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Incorrect 2 ms 2764 KB Output isn't correct
8 Halted 0 ms 0 KB -