oj.uz

Submission #1059593

# Submission time Handle Problem Language Result Execution time Memory
1059593 2024-08-15T05:49:28 Z vjudge1 Duathlon (APIO18_duathlon) C++17
0 / 100
 1000 ms 173900 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-=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=N=n;
    for(int K=1;K<=n;K++) {
        if(dep[K])continue;
        Rt[K]=1;
        dfsC(1,0);
        dfsM(1,0);
    }
    for(int i=1;i<=n;i++) if(cycpar[i])
        adj2[dsu.abp(cycpar[i])].push_back(i);
    for(int i=1;i<=N;i++)
        if(Rt[i])dfsA(1);
    cout<<TOT<<'\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 15960 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 15960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 42968 KB Output is correct
2 Correct 63 ms 42452 KB Output is correct
3 Execution timed out 1025 ms 32144 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15708 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 3 ms 17708 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 3 ms 17756 KB Output is correct
6 Correct 7 ms 16008 KB Output is correct
7 Correct 8 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 Execution timed out 1062 ms 18012 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 23892 KB Output is correct
2 Correct 34 ms 23900 KB Output is correct
3 Correct 37 ms 23892 KB Output is correct
4 Correct 55 ms 23888 KB Output is correct
5 Correct 41 ms 23888 KB Output is correct
6 Correct 47 ms 33876 KB Output is correct
7 Correct 41 ms 30296 KB Output is correct
8 Correct 41 ms 28508 KB Output is correct
9 Correct 42 ms 26964 KB Output is correct
10 Execution timed out 1082 ms 173900 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17752 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 3 ms 17756 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 3 ms 17756 KB Output is correct
6 Correct 3 ms 17756 KB Output is correct
7 Correct 4 ms 17756 KB Output is correct
8 Correct 3 ms 17868 KB Output is correct
9 Correct 3 ms 17756 KB Output is correct
10 Correct 3 ms 17756 KB Output is correct
11 Correct 3 ms 17756 KB Output is correct
12 Correct 3 ms 17756 KB Output is correct
13 Correct 3 ms 17756 KB Output is correct
14 Correct 3 ms 17752 KB Output is correct
15 Correct 3 ms 17756 KB Output is correct
16 Execution timed out 1099 ms 18012 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 23888 KB Output is correct
2 Correct 35 ms 24140 KB Output is correct
3 Correct 45 ms 26204 KB Output is correct
4 Correct 47 ms 27164 KB Output is correct
5 Correct 46 ms 27732 KB Output is correct
6 Correct 46 ms 27728 KB Output is correct
7 Correct 45 ms 27832 KB Output is correct
8 Correct 44 ms 27840 KB Output is correct
9 Correct 43 ms 27728 KB Output is correct
10 Correct 44 ms 27848 KB Output is correct
11 Correct 46 ms 27728 KB Output is correct
12 Correct 42 ms 27984 KB Output is correct
13 Correct 41 ms 27984 KB Output is correct
14 Correct 54 ms 31572 KB Output is correct
15 Correct 53 ms 33108 KB Output is correct
16 Correct 49 ms 30800 KB Output is correct
17 Correct 66 ms 33108 KB Output is correct
18 Correct 53 ms 31136 KB Output is correct
19 Execution timed out 1065 ms 87504 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 15960 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 15960 KB Output isn't correct
2 Halted 0 ms 0 KB -