oj.uz

답안 #1114761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114761 2024-11-19T14:42:02 Z asli_bg 철인 이종 경기 (APIO18_duathlon) C++11
0 / 100
 99 ms 47976 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sp <<' '<<
#define pb push_back

#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define cont(a) for(auto el:a) cout<<el<<' '; cout<<endl;
#define contp(a) for(auto el:a) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;

#define DEBUG(x) cout<<#x sp ":" sp x<<endl;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef long long ll;

#define endl '\n'
#define mid (l+r)/2

const int MAXN=4e5+5;

int n,m;
vi adj[MAXN];
int ans;

/*----------BLOCK-CUT TREE----------- */

bool vis[MAXN], isarc[MAXN];
int dep[MAXN], low[MAXN];

vi st;

vi bcc[MAXN];

int cnt; //şuanki grafta kaç eleman var

int ind;

void dfs(int nd, int ata,int h){
    dep[nd]=h;
    low[nd]=h;

    int ch=0;
    st.pb(nd);

    cnt++;

    for(auto kom:adj[nd]){
        if(kom==ata) continue;
        if(vis[kom]){
            if(dep[kom]<dep[nd]) low[nd]=min(low[nd],dep[kom]);
            continue;
        }

        vis[kom]=true;
        dfs(kom,nd,h+1);
        
        ch++;

        if(low[kom]>=dep[nd]){ //we should create new block
            //komsuyu tüm graftan ayıran node == nd

            ind++;
            bcc[nd].pb(ind); //nodedan yeni bloğa

            int el;  
            do{
                el=st.back();
                st.pop_back();
                bcc[ind].pb(el);
            }while(el!=kom); //bloktan elemanlara edge çek

            if(ata!=-1) isarc[nd]=true;
        }

        low[nd]=min(low[nd],low[kom]);
    }

    if(ata==-1 and ch>1) isarc[nd]=true; 
}

/*----------DFS----------- */

int sub[MAXN];
bool vis2[MAXN];

void dfs2(int nd,int ata){

    sub[nd]=(nd<=n); //ben blok muyum yoksa node muyum

    for(auto kom:bcc[nd]){
        if(kom==ata) continue;
        if(vis2[kom]) continue;

        vis2[kom]=true;
        dfs2(kom,nd);
        sub[nd]+=sub[kom];

        if(nd>n){
            //ben bloksam
            //bcc[nd].size() --> bende kaç eleman var
            int bir=bcc[nd].size(); //bu bloktan 1 tane
            int iki=sub[kom]*(sub[kom]-1); //subtreemdeki nodelardan 2 tane seç

            ans-=max(0LL,bir*iki);
        }
    }

    //beni root kabul edip hesaplama yapıyorum
    //benim üstümde kalan subtreeyi hesaplamadık

    if(nd>n){
        int bir=bcc[nd].size();
        int iki=(cnt-sub[nd])*(cnt-sub[nd]-1);
        ans-=bir*iki;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    FOR(i,m){
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    ans=n*(n-1)*(n-2);

    ind=n;

    FORE(j,1,n+1){
        if(!vis[j]){
            cnt=0;
            st.clear();

            vis[j]=true;

            dfs(j,-1,0);

            dfs2(j,-1);
        }
    }

    cout<<ans<<endl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 45388 KB Output is correct
2 Correct 46 ms 45280 KB Output is correct
3 Incorrect 51 ms 43076 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 27472 KB Output is correct
2 Correct 5 ms 27472 KB Output is correct
3 Correct 5 ms 27472 KB Output is correct
4 Correct 5 ms 27728 KB Output is correct
5 Correct 5 ms 27540 KB Output is correct
6 Correct 5 ms 27728 KB Output is correct
7 Correct 5 ms 27728 KB Output is correct
8 Correct 7 ms 27728 KB Output is correct
9 Correct 6 ms 27472 KB Output is correct
10 Incorrect 5 ms 27640 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 38296 KB Output is correct
2 Correct 57 ms 38476 KB Output is correct
3 Correct 58 ms 38388 KB Output is correct
4 Correct 57 ms 38472 KB Output is correct
5 Correct 57 ms 38476 KB Output is correct
6 Correct 99 ms 47976 KB Output is correct
7 Correct 74 ms 44736 KB Output is correct
8 Correct 67 ms 43180 KB Output is correct
9 Correct 65 ms 41656 KB Output is correct
10 Incorrect 61 ms 38472 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 27472 KB Output is correct
2 Correct 5 ms 27472 KB Output is correct
3 Correct 5 ms 27540 KB Output is correct
4 Correct 5 ms 27472 KB Output is correct
5 Correct 6 ms 27472 KB Output is correct
6 Correct 5 ms 27472 KB Output is correct
7 Correct 7 ms 27472 KB Output is correct
8 Correct 5 ms 27472 KB Output is correct
9 Correct 5 ms 27472 KB Output is correct
10 Correct 5 ms 27472 KB Output is correct
11 Correct 5 ms 27472 KB Output is correct
12 Correct 6 ms 27904 KB Output is correct
13 Correct 5 ms 27472 KB Output is correct
14 Correct 5 ms 27484 KB Output is correct
15 Correct 5 ms 27472 KB Output is correct
16 Incorrect 5 ms 27472 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 38472 KB Output is correct
2 Correct 58 ms 38604 KB Output is correct
3 Correct 65 ms 37960 KB Output is correct
4 Correct 54 ms 36936 KB Output is correct
5 Correct 51 ms 35812 KB Output is correct
6 Correct 50 ms 35156 KB Output is correct
7 Correct 58 ms 34888 KB Output is correct
8 Correct 69 ms 34632 KB Output is correct
9 Correct 55 ms 34376 KB Output is correct
10 Correct 63 ms 34444 KB Output is correct
11 Correct 38 ms 34120 KB Output is correct
12 Correct 36 ms 34128 KB Output is correct
13 Correct 33 ms 34220 KB Output is correct
14 Correct 50 ms 36976 KB Output is correct
15 Correct 97 ms 44480 KB Output is correct
16 Correct 84 ms 42220 KB Output is correct
17 Correct 70 ms 42944 KB Output is correct
18 Correct 79 ms 41160 KB Output is correct
19 Incorrect 57 ms 37084 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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