oj.uz

답안 #772001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772001 2023-07-03T13:39:04 Z gagik_2007 철인 이종 경기 (APIO18_duathlon) C++17
10 / 100
 1000 ms 25676 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=3e5+7;
const ll LG=25;
ll n,m,k;
vector<int>g[N];
bool used[N];
bool cikli_papa[N];
int cikl[N];
int a[N];
vector<int>cikler;
set<pair<int,int>>koxer;
vector<int>gg[N];
int up[N][LG];
int dist[N][LG];
int tin[N],tout[N];
int timer=0;
bool arinq[N];
int comp[N];

int ciklGti(int p, int v, int par){
    used[v]=true;
    for(int to:g[v]){
        if(!used[to]){
            int res=ciklGti(p, to, v);
            if(res!=-1){
                if(cikli_papa[v])cikl[p]=v;
                return res + 1;
            }
        }
        else if(to==p&&to!=par){
            if(cikli_papa[v])cikl[p]=v;
            return 1;
        }
    }
    return -1;
}

void dfs(int v, int par=-1){
    tin[v]=timer++;
    up[v][0]=(par==-1?v:par);
    dist[v][0]=(par==-1?0:a[par]);
    for(int to:gg[v]){
        if(to!=par){
            dfs(to,v);
        }
    }
    tout[v]=timer++;
}

bool is_papa(int v, int u){
    return (tin[v]<=tin[u]&&tout[v]>=tout[u]);
}

void lca_precalc() {
    for(int i=1;i<LG;i++){
        for(int v=1;v<=n;v++){
            up[v][i]=up[up[v][i-1]][i-1];
            dist[v][i]=dist[v][i-1]+dist[up[v][i-1]][i-1];
        }
    }
}

int lca(int v, int u){
    if(is_papa(v,u))return v;
    if(is_papa(u,v))return u;
    for(int i=LG-1;i>=0;i--){
        if(!is_papa(up[v][i],u)){
            v=up[v][i];
        }
    }
    return up[v][0];
}

int find_dist(int v, int u){
    if(v==u)return a[v];
    int papa=lca(u,v);
    int ans=0;
    for(int i=LG-1;i>=0;i--){
        if(!is_papa(up[v][i],papa)){
            ans+=dist[v][i];
            v=up[v][i];
        }
    }
    for(int i=LG-1;i>=0;i--){
        if(!is_papa(up[u][i],papa)){
            ans+=dist[u][i];
            u=up[u][i];
        }
    }
    ans+=a[v];
    ans+=a[u];
    if(papa!=v&&papa!=u){
        ans+=a[papa];
    }
    return ans;
}

void findComp(int c, int v){
    comp[v]=c;
    for(int to:g[v]){
        if(comp[to]==0){
            findComp(c,to);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    // auto start = std::chrono::high_resolution_clock::now();
    for(int v=1;v<=n;v++){
        fill(used,used+n+1,false);
        int res=ciklGti(v,v,v);
        if(res!=-1){
            if(cikl[v]==0){
                cikl[v]=v;
                cikli_papa[v]=true;
                cikler.push_back(v);
                a[v]=res;
            }
        }
        else{
            cikl[v]=v;
            cikler.push_back(v);
            a[v]=1;
        }
    }
    // cout<<endl;
    // for(int v:cikler)cout<<v<<" "<<a[v]<<endl;
    // cout<<endl;
    // for(int v=1;v<=n;v++){
    //     cout<<cikl[v]<<" ";
    // }
    // cout<<endl;
    for(int v=1;v<=n;v++){
        for(int to:g[v]){
            if(cikl[v]!=cikl[to])
            koxer.insert({cikl[v],cikl[to]});
            if(cikl[v]!=cikl[to])
            koxer.insert({cikl[to],cikl[v]});
        }
    }
    for(auto e:koxer){
        // cout<<e.ff<<" "<<e.ss<<endl;
        gg[e.ff].push_back(e.ss);
    }
    // auto end = std::chrono::high_resolution_clock::now();
    // auto dur = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
    // cout<<dur.count()<<" microseconds "<<endl;
    for(int v:cikler){
        if(tout[v]==0){
            dfs(v);
        }
    }
    lca_precalc();
    int cur=1;
    for(int v=1;v<=n;v++){
        if(comp[v]==0){
            findComp(cur++,v);
        }
    }
    ll ans=0;
    for(int v:cikler){
        for(int u:cikler){
            if(u!=v&&comp[u]==comp[v]){
                int cur=find_dist(u,v);
                ans+=cur-a[u]-a[v];
                ans+=(cur-a[u]-1)*(a[v]-1);
                ans+=(cur-a[v]-1)*(a[u]-1);
                ans+=(cur-2)*(a[v]-1)*(a[u]-1);
            }
        }
    }
    for(int v:cikler){
        ans+=a[v]*(a[v]-1)*(a[v]-2);
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 25676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 14836 KB Output is correct
2 Correct 243 ms 14812 KB Output is correct
3 Correct 244 ms 14836 KB Output is correct
4 Correct 207 ms 14908 KB Output is correct
5 Correct 234 ms 14880 KB Output is correct
6 Correct 238 ms 14868 KB Output is correct
7 Correct 226 ms 14912 KB Output is correct
8 Correct 246 ms 14884 KB Output is correct
9 Correct 250 ms 14868 KB Output is correct
10 Correct 206 ms 14832 KB Output is correct
11 Correct 189 ms 14812 KB Output is correct
12 Correct 102 ms 14836 KB Output is correct
13 Correct 46 ms 14804 KB Output is correct
14 Correct 14 ms 14840 KB Output is correct
15 Correct 10 ms 14756 KB Output is correct
16 Correct 9 ms 14680 KB Output is correct
17 Correct 212 ms 14848 KB Output is correct
18 Correct 224 ms 14892 KB Output is correct
19 Correct 228 ms 14856 KB Output is correct
20 Correct 230 ms 14772 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1083 ms 18004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 14836 KB Output is correct
2 Correct 245 ms 14852 KB Output is correct
3 Incorrect 117 ms 14812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1072 ms 17756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -