oj.uz

Submission #1059602

# Submission time Handle Problem Language Result Execution time Memory
1059602 2024-08-15T06:01:03 Z vjudge1 Duathlon (APIO18_duathlon) C++17
0 / 100
 81 ms 42616 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],N2;
void dfsC(int n,int p){
    N++;
    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);
}
void dfsP(int n,int p){
    for(auto i:adj[n])
        if(par[i]==n)
            dfsP(i,n);
    if(cycpar[n])
        adj2[dsu.abp(cycpar[n])].push_back(n);
}
long long TOT;
void dfsA(int n){
    sz[n]=n<=N2;
    long long k=(1ll*N-sz[n])*(N-sz[n]);
    for(auto i:adj2[n])dfsA(i),
        sz[n]+=sz[i],k-=sz[i]*1ll*sz[i];
    k-=(1ll*N-sz[n])*(N-sz[n]);
    if(n>N)k*=adj2[n].size()-1;
    TOT+=k;
}
bitset<100100>Rt;
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=N2=n;
    for(int K=1;K<=n;K++) {
        if(dep[K])continue;
        N=0;
        Rt[K]=1;
        dfsC(K,0);
        dfsM(K,0);
        dfsP(K,0);
        dfsA(K);
    }
    cout<<TOT<<'\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15708 KB Output is correct
2 Correct 6 ms 15672 KB Output is correct
3 Correct 6 ms 15704 KB Output is correct
4 Correct 6 ms 15708 KB Output is correct
5 Correct 6 ms 15708 KB Output is correct
6 Correct 6 ms 15732 KB Output is correct
7 Correct 6 ms 15708 KB Output is correct
8 Correct 6 ms 15816 KB Output is correct
9 Correct 6 ms 15708 KB Output is correct
10 Correct 7 ms 15708 KB Output is correct
11 Correct 6 ms 15708 KB Output is correct
12 Correct 6 ms 15708 KB Output is correct
13 Correct 8 ms 15708 KB Output is correct
14 Correct 6 ms 15632 KB Output is correct
15 Correct 6 ms 15708 KB Output is correct
16 Correct 6 ms 15708 KB Output is correct
17 Correct 7 ms 15840 KB Output is correct
18 Correct 8 ms 15708 KB Output is correct
19 Incorrect 7 ms 15708 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15708 KB Output is correct
2 Correct 6 ms 15672 KB Output is correct
3 Correct 6 ms 15704 KB Output is correct
4 Correct 6 ms 15708 KB Output is correct
5 Correct 6 ms 15708 KB Output is correct
6 Correct 6 ms 15732 KB Output is correct
7 Correct 6 ms 15708 KB Output is correct
8 Correct 6 ms 15816 KB Output is correct
9 Correct 6 ms 15708 KB Output is correct
10 Correct 7 ms 15708 KB Output is correct
11 Correct 6 ms 15708 KB Output is correct
12 Correct 6 ms 15708 KB Output is correct
13 Correct 8 ms 15708 KB Output is correct
14 Correct 6 ms 15632 KB Output is correct
15 Correct 6 ms 15708 KB Output is correct
16 Correct 6 ms 15708 KB Output is correct
17 Correct 7 ms 15840 KB Output is correct
18 Correct 8 ms 15708 KB Output is correct
19 Incorrect 7 ms 15708 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 42448 KB Output is correct
2 Correct 77 ms 42616 KB Output is correct
3 Incorrect 67 ms 33740 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 23108 KB Output is correct
2 Correct 47 ms 23124 KB Output is correct
3 Correct 45 ms 23124 KB Output is correct
4 Correct 45 ms 23136 KB Output is correct
5 Correct 45 ms 23032 KB Output is correct
6 Correct 65 ms 32932 KB Output is correct
7 Correct 59 ms 29268 KB Output is correct
8 Correct 55 ms 27732 KB Output is correct
9 Correct 55 ms 26200 KB Output is correct
10 Incorrect 54 ms 23128 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 22976 KB Output is correct
2 Correct 52 ms 23220 KB Output is correct
3 Correct 66 ms 25828 KB Output is correct
4 Correct 67 ms 26960 KB Output is correct
5 Correct 64 ms 27216 KB Output is correct
6 Correct 68 ms 27220 KB Output is correct
7 Correct 76 ms 27472 KB Output is correct
8 Correct 67 ms 27208 KB Output is correct
9 Correct 63 ms 27208 KB Output is correct
10 Correct 65 ms 27220 KB Output is correct
11 Correct 63 ms 27172 KB Output is correct
12 Correct 61 ms 27476 KB Output is correct
13 Correct 59 ms 27472 KB Output is correct
14 Correct 65 ms 31056 KB Output is correct
15 Correct 72 ms 32576 KB Output is correct
16 Correct 72 ms 30400 KB Output is correct
17 Correct 81 ms 32864 KB Output is correct
18 Correct 70 ms 30804 KB Output is correct
19 Incorrect 71 ms 26932 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15708 KB Output is correct
2 Correct 6 ms 15672 KB Output is correct
3 Correct 6 ms 15704 KB Output is correct
4 Correct 6 ms 15708 KB Output is correct
5 Correct 6 ms 15708 KB Output is correct
6 Correct 6 ms 15732 KB Output is correct
7 Correct 6 ms 15708 KB Output is correct
8 Correct 6 ms 15816 KB Output is correct
9 Correct 6 ms 15708 KB Output is correct
10 Correct 7 ms 15708 KB Output is correct
11 Correct 6 ms 15708 KB Output is correct
12 Correct 6 ms 15708 KB Output is correct
13 Correct 8 ms 15708 KB Output is correct
14 Correct 6 ms 15632 KB Output is correct
15 Correct 6 ms 15708 KB Output is correct
16 Correct 6 ms 15708 KB Output is correct
17 Correct 7 ms 15840 KB Output is correct
18 Correct 8 ms 15708 KB Output is correct
19 Incorrect 7 ms 15708 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15708 KB Output is correct
2 Correct 6 ms 15672 KB Output is correct
3 Correct 6 ms 15704 KB Output is correct
4 Correct 6 ms 15708 KB Output is correct
5 Correct 6 ms 15708 KB Output is correct
6 Correct 6 ms 15732 KB Output is correct
7 Correct 6 ms 15708 KB Output is correct
8 Correct 6 ms 15816 KB Output is correct
9 Correct 6 ms 15708 KB Output is correct
10 Correct 7 ms 15708 KB Output is correct
11 Correct 6 ms 15708 KB Output is correct
12 Correct 6 ms 15708 KB Output is correct
13 Correct 8 ms 15708 KB Output is correct
14 Correct 6 ms 15632 KB Output is correct
15 Correct 6 ms 15708 KB Output is correct
16 Correct 6 ms 15708 KB Output is correct
17 Correct 7 ms 15840 KB Output is correct
18 Correct 8 ms 15708 KB Output is correct
19 Incorrect 7 ms 15708 KB Output isn't correct
20 Halted 0 ms 0 KB -