oj.uz

답안 #1114757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114757 2024-11-19T14:36:46 Z asli_bg 철인 이종 경기 (APIO18_duathlon) C++11
0 / 100
 66 ms 40640 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=3e5+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;
            vis[j]=true;

            dfs(j,-1,0);

            dfs2(j,-1);
        }
    }

    cout<<ans<<endl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 37952 KB Output is correct
2 Correct 49 ms 37932 KB Output is correct
3 Incorrect 49 ms 35828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 31020 KB Output is correct
2 Correct 44 ms 31048 KB Output is correct
3 Correct 46 ms 31048 KB Output is correct
4 Correct 52 ms 31048 KB Output is correct
5 Correct 47 ms 31048 KB Output is correct
6 Correct 64 ms 40640 KB Output is correct
7 Correct 61 ms 37380 KB Output is correct
8 Correct 66 ms 35780 KB Output is correct
9 Correct 57 ms 34244 KB Output is correct
10 Incorrect 53 ms 31040 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 31052 KB Output is correct
2 Correct 49 ms 31304 KB Output is correct
3 Correct 46 ms 30536 KB Output is correct
4 Correct 65 ms 29768 KB Output is correct
5 Correct 48 ms 28488 KB Output is correct
6 Correct 43 ms 27984 KB Output is correct
7 Correct 48 ms 27720 KB Output is correct
8 Correct 37 ms 27208 KB Output is correct
9 Correct 39 ms 27216 KB Output is correct
10 Correct 37 ms 26952 KB Output is correct
11 Correct 37 ms 27028 KB Output is correct
12 Correct 34 ms 26972 KB Output is correct
13 Correct 37 ms 26952 KB Output is correct
14 Correct 37 ms 29640 KB Output is correct
15 Correct 62 ms 37208 KB Output is correct
16 Correct 57 ms 34828 KB Output is correct
17 Correct 66 ms 35700 KB Output is correct
18 Correct 59 ms 33740 KB Output is correct
19 Incorrect 55 ms 29768 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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