oj.uz

Submission #744462

# Submission time Handle Problem Language Result Execution time Memory
744462 2023-05-18T15:16:29 Z Abito Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define ep insert
#define pow pwr
#define sqrt sqrtt
#define elif else if
#define y1 YONE
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,sz[N],par[N],dpar[N],dsz[N];
vector<int> adj[N];
int getpar(int x){
    if (x==dpar[x]) return x;
    return dpar[x]=getpar(dpar[x]);
}
void link(int x,int y){
    x=getpar(x);y=getpar(y);
    if (x==y) return;
    if (dsz[x]>dsz[y]) swap(x,y);
    dpar[x]=y;
    dsz[y]+=dsz[x];
    return;
}
int getsize(int node,int p){
    par[node]=p;
    sz[node]=1;
    for (auto u:adj[node]){
        if (u==p) continue;
        sz[node]+=getsize(u,node);
    }return sz[node];
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        dsz[i]=1;
        dpar[i]=i;
    }
    for (int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
        link(x,y);
    }
    for (int i=1;i<=n;i++){
        if (sz[i]) continue;
        getsize(i,0);
    }
    int ans=0;
    for (int i=1;i<=n;i++){
        int x=sz[i]-1;
        for (auto u:adj[i]){
            if (u==par[i]) continue;
            x-=sz[u];
            ans+=x*sz[u];
        }ans+=(dsz[getpar(i)]-sz[i])*(sz[i]-1);
    }
    cout<<ans*2LL<<endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 540 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 540 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 1055 ms 338676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23892 KB Output is correct
2 Correct 14 ms 23824 KB Output is correct
3 Correct 14 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 13 ms 23884 KB Output is correct
6 Correct 14 ms 23900 KB Output is correct
7 Correct 15 ms 23892 KB Output is correct
8 Correct 14 ms 23892 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Correct 18 ms 23892 KB Output is correct
11 Correct 16 ms 23892 KB Output is correct
12 Correct 16 ms 23804 KB Output is correct
13 Correct 15 ms 23820 KB Output is correct
14 Correct 14 ms 23808 KB Output is correct
15 Correct 14 ms 23800 KB Output is correct
16 Correct 13 ms 23892 KB Output is correct
17 Correct 14 ms 23824 KB Output is correct
18 Correct 14 ms 23820 KB Output is correct
19 Correct 14 ms 23828 KB Output is correct
20 Correct 13 ms 23892 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 31272 KB Output is correct
2 Correct 74 ms 31212 KB Output is correct
3 Correct 95 ms 31252 KB Output is correct
4 Correct 79 ms 31180 KB Output is correct
5 Correct 69 ms 31264 KB Output is correct
6 Correct 72 ms 33228 KB Output is correct
7 Correct 74 ms 32840 KB Output is correct
8 Correct 72 ms 32368 KB Output is correct
9 Correct 73 ms 31948 KB Output is correct
10 Correct 64 ms 31264 KB Output is correct
11 Correct 68 ms 31876 KB Output is correct
12 Correct 68 ms 31820 KB Output is correct
13 Correct 78 ms 31888 KB Output is correct
14 Correct 68 ms 31548 KB Output is correct
15 Correct 58 ms 31244 KB Output is correct
16 Correct 44 ms 29996 KB Output is correct
17 Correct 49 ms 32064 KB Output is correct
18 Correct 51 ms 32036 KB Output is correct
19 Correct 51 ms 32044 KB Output is correct
20 Correct 49 ms 32024 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23892 KB Output is correct
2 Correct 15 ms 23836 KB Output is correct
3 Runtime error 629 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 79 ms 31244 KB Output is correct
2 Correct 65 ms 31120 KB Output is correct
3 Runtime error 776 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 540 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 540 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -