oj.uz

Submission #1059586

# Submission time Handle Problem Language Result Execution time Memory
1059586 2024-08-15T05:44:36 Z vjudge1 Duathlon (APIO18_duathlon) C++17
0 / 100
 77 ms 42524 KB 
#include<bits/stdc++.h>
using namespace std;
struct DDS{
    int par[1<<18];
    int abp(int n){
        return par[n]?par[n]=abp(par[n]):n;
    }
    void merge(int a,int b){
        a=abp(a),b=abp(b);
        if(a-b)par[a]=b;
    }
} dsu;
vector<int>adj[1<<17],adj2[1<<18];
set<pair<int,int>>st[1<<17];
int par[1<<17],dep[1<<17],cycpar[1<<17],CC,N,sz[1<<17];
void dfsC(int n,int p){
    dep[n]=dep[p]+1;
    par[n]=p;
    for(auto i:adj[n]){
        if(i==p)continue;
        if(!dep[i])
            dfsC(i,n);
        else if(dep[i]<dep[n])
            st[n].insert({dep[i],++CC});
    }
}
void dfsM(int n,int p){
    for(auto i:adj[n]) {
        if(par[i]-n)continue;
        dfsM(i,n);
        if(st[i].empty())continue;
        if(st[i].begin()->first<dep[n]) {
            if(st[n].size())
                dsu.merge(st[i].begin()->second,st[n].begin()->second);
            st[n].insert(*st[i].begin());
        } else adj2[n].push_back(dsu.abp(st[i].begin()->second));
    }
    if(st[n].size())
        cycpar[n]=st[n].begin()->second;
    else adj2[p].push_back(n);
}
long long TOT;
void dfsA(int n){
    sz[n]=n<=N;
    long long k=1ll*(N-sz[n])*(N-sz[n]);
    for(auto i:adj2[n])dfsA(i),
        sz[n]+=sz[i],k-=1ll*sz[i]*sz[i];
    k-=1ll*(N-sz[n])*(N-sz[n]);
    if(n>N)k*=adj2[n].size()-1;
    TOT+=k;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    CC=N=n;
    dfsC(1,0);
    dfsM(1,0);
    for(int i=1;i<=n;i++) if(cycpar[i])
        adj2[dsu.abp(cycpar[i])].push_back(i);
    dfsA(1);
    cout<<TOT<<'\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 15708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 15708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 42524 KB Output is correct
2 Correct 70 ms 42452 KB Output is correct
3 Incorrect 52 ms 32052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15844 KB Output is correct
2 Correct 6 ms 15708 KB Output is correct
3 Correct 6 ms 15708 KB Output is correct
4 Correct 9 ms 15992 KB Output is correct
5 Correct 7 ms 15964 KB Output is correct
6 Correct 7 ms 15964 KB Output is correct
7 Correct 6 ms 15964 KB Output is correct
8 Correct 7 ms 15964 KB Output is correct
9 Correct 6 ms 15964 KB Output is correct
10 Incorrect 8 ms 15924 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 22916 KB Output is correct
2 Correct 53 ms 23124 KB Output is correct
3 Correct 48 ms 23120 KB Output is correct
4 Correct 53 ms 23124 KB Output is correct
5 Correct 48 ms 23064 KB Output is correct
6 Correct 65 ms 33020 KB Output is correct
7 Correct 58 ms 29204 KB Output is correct
8 Correct 55 ms 27732 KB Output is correct
9 Correct 59 ms 26196 KB Output is correct
10 Incorrect 43 ms 22364 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15708 KB Output is correct
2 Correct 6 ms 15812 KB Output is correct
3 Correct 6 ms 15900 KB Output is correct
4 Correct 7 ms 15964 KB Output is correct
5 Correct 6 ms 15872 KB Output is correct
6 Correct 10 ms 15992 KB Output is correct
7 Correct 11 ms 15964 KB Output is correct
8 Correct 8 ms 15964 KB Output is correct
9 Correct 7 ms 15964 KB Output is correct
10 Correct 7 ms 15964 KB Output is correct
11 Correct 6 ms 15964 KB Output is correct
12 Correct 6 ms 15964 KB Output is correct
13 Correct 9 ms 15964 KB Output is correct
14 Correct 7 ms 15800 KB Output is correct
15 Correct 6 ms 15964 KB Output is correct
16 Incorrect 8 ms 15708 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 22960 KB Output is correct
2 Correct 48 ms 23384 KB Output is correct
3 Correct 77 ms 25988 KB Output is correct
4 Correct 73 ms 26952 KB Output is correct
5 Correct 73 ms 27244 KB Output is correct
6 Correct 67 ms 27480 KB Output is correct
7 Correct 62 ms 27256 KB Output is correct
8 Correct 64 ms 27300 KB Output is correct
9 Correct 73 ms 27164 KB Output is correct
10 Correct 61 ms 27220 KB Output is correct
11 Correct 62 ms 27216 KB Output is correct
12 Correct 63 ms 27472 KB Output is correct
13 Correct 55 ms 27536 KB Output is correct
14 Correct 76 ms 31084 KB Output is correct
15 Correct 73 ms 32580 KB Output is correct
16 Correct 71 ms 30264 KB Output is correct
17 Correct 71 ms 32852 KB Output is correct
18 Correct 75 ms 30648 KB Output is correct
19 Incorrect 70 ms 26592 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 15708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 15708 KB Output isn't correct
2 Halted 0 ms 0 KB -