oj.uz

Submission #260875

# Submission time Handle Problem Language Result Execution time Memory
260875 2020-08-11T06:32:00 Z emanIaicepsa Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define vi vector<int>
#define pb emplace_back
#define fi first
#define se second
#define all(n) (n).begin(),(n).end()
#define mem(n,m) memset(n,m,sizeof(n))
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename A> void _do(A x){cerr<<x<<'\n';}
template<typename A,typename ...B> void _do(A x,B ...y){cerr<<x<<", ";_do(y...);}

ll n,m;
vi E[100005];
ll siz[100005], ans=0;
bool vis[100005];

void dfs(int x,int p){
    vis[x] = 1;
    siz[x] = 1;
    for(auto i:E[x]){
        if(i==p) continue;
        dfs(i,x);
        siz[x] += siz[i];
    }
}

void dfs2(int x,int p,int anc){
    vis[x] = 1;
    for(auto i:E[x]){
        if(i==p) continue;
        dfs2(i,x,anc);
        ans += siz[i] * (siz[anc]-siz[i]-1);
    }
    ans += (siz[x]-1) * (siz[anc]-siz[x]);
}

signed main(){
	IOS;
    cin>>n>>m;
    for(int i=1,a,b;i<=m;i++){
        cin>>a>>b;
        E[a].pb(b);
        E[b].pb(a);
    }

    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);
    mem(vis,0);
    for(int i=1;i<=n;i++) if(!vis[i]) dfs2(i,0,i);

    cout<<ans<<'\n';

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 559 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 559 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1126 ms 407416 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 2816 KB Output is correct
2 Correct 3 ms 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 2 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 3 ms 2816 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 4 ms 2816 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct
14 Correct 3 ms 2816 KB Output is correct
15 Correct 2 ms 2816 KB Output is correct
16 Correct 2 ms 2816 KB Output is correct
17 Correct 3 ms 2816 KB Output is correct
18 Correct 3 ms 2816 KB Output is correct
19 Correct 2 ms 2816 KB Output is correct
20 Correct 2 ms 2816 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 6776 KB Output is correct
2 Correct 64 ms 6776 KB Output is correct
3 Correct 71 ms 6776 KB Output is correct
4 Correct 77 ms 6772 KB Output is correct
5 Correct 62 ms 6776 KB Output is correct
6 Correct 85 ms 11092 KB Output is correct
7 Correct 91 ms 9592 KB Output is correct
8 Correct 87 ms 8824 KB Output is correct
9 Correct 77 ms 8056 KB Output is correct
10 Correct 66 ms 6776 KB Output is correct
11 Correct 67 ms 8056 KB Output is correct
12 Correct 77 ms 8056 KB Output is correct
13 Correct 78 ms 8184 KB Output is correct
14 Correct 78 ms 7848 KB Output is correct
15 Correct 61 ms 7672 KB Output is correct
16 Correct 33 ms 6520 KB Output is correct
17 Correct 43 ms 8304 KB Output is correct
18 Correct 46 ms 8432 KB Output is correct
19 Correct 46 ms 8300 KB Output is correct
20 Correct 46 ms 8312 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2816 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Runtime error 693 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 6776 KB Output is correct
2 Correct 84 ms 6684 KB Output is correct
3 Runtime error 888 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 559 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 559 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -