oj.uz

Submission #402166

# Submission time Handle Problem Language Result Execution time Memory
402166 2021-05-11T11:45:58 Z A_D Duathlon (APIO18_duathlon) C++14
23 / 100
 141 ms 12360 KB 

#include <bits/stdc++.h>

#define int long long

using namespace std;
const int N=1e5+100;
vector<int> g[N];
bool vis[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(x==p)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 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];
//            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:40:11: warning: unused variable 'ann' [-Wunused-variable]
   40 |     int m,ann=0;
      |           ^~~
count_triplets.cpp: At global scope:
count_triplets.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main()
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

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 2764 KB Output is correct
3 Correct 3 ms 2800 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2780 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 3 ms 2764 KB Output is correct
13 Correct 3 ms 2788 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 2792 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 106 ms 8744 KB Output is correct
2 Correct 110 ms 8768 KB Output is correct
3 Correct 109 ms 8692 KB Output is correct
4 Correct 108 ms 8900 KB Output is correct
5 Correct 141 ms 8776 KB Output is correct
6 Correct 122 ms 12360 KB Output is correct
7 Correct 124 ms 11592 KB Output is correct
8 Correct 115 ms 10728 KB Output is correct
9 Correct 137 ms 10116 KB Output is correct
10 Correct 119 ms 8848 KB Output is correct
11 Correct 105 ms 10048 KB Output is correct
12 Correct 138 ms 10060 KB Output is correct
13 Correct 105 ms 10052 KB Output is correct
14 Correct 96 ms 9720 KB Output is correct
15 Correct 84 ms 9296 KB Output is correct
16 Correct 53 ms 8076 KB Output is correct
17 Correct 106 ms 10380 KB Output is correct
18 Correct 85 ms 10272 KB Output is correct
19 Correct 92 ms 10196 KB Output is correct
20 Correct 91 ms 10256 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 3 ms 2764 KB Output is correct
3 Runtime error 5 ms 5196 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 8800 KB Output is correct
2 Correct 109 ms 8696 KB Output is correct
3 Runtime error 6 ms 5196 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -