oj.uz

Submission #1114753

# Submission time Handle Problem Language Result Execution time Memory
1114753 2024-11-19T14:35:31 Z asli_bg Duathlon (APIO18_duathlon) C++11
0 / 100
 73 ms 40624 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]){
            vis[j]=true;

            dfs(j,-1,0);

            dfs2(j,-1);
        }
    }

    cout<<ans<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 20048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 20048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 37960 KB Output is correct
2 Correct 53 ms 37976 KB Output is correct
3 Incorrect 50 ms 35692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22352 KB Output is correct
2 Correct 5 ms 22352 KB Output is correct
3 Correct 5 ms 22352 KB Output is correct
4 Correct 6 ms 22352 KB Output is correct
5 Correct 6 ms 22352 KB Output is correct
6 Correct 5 ms 22352 KB Output is correct
7 Correct 4 ms 22352 KB Output is correct
8 Correct 5 ms 22352 KB Output is correct
9 Correct 6 ms 22516 KB Output is correct
10 Incorrect 6 ms 22352 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31048 KB Output is correct
2 Correct 51 ms 31044 KB Output is correct
3 Correct 55 ms 31104 KB Output is correct
4 Correct 45 ms 31008 KB Output is correct
5 Correct 49 ms 30964 KB Output is correct
6 Correct 64 ms 40624 KB Output is correct
7 Correct 61 ms 37312 KB Output is correct
8 Correct 73 ms 35780 KB Output is correct
9 Correct 63 ms 34136 KB Output is correct
10 Incorrect 48 ms 30976 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22352 KB Output is correct
2 Correct 5 ms 22352 KB Output is correct
3 Correct 4 ms 22352 KB Output is correct
4 Correct 5 ms 22352 KB Output is correct
5 Correct 5 ms 22352 KB Output is correct
6 Correct 4 ms 22352 KB Output is correct
7 Correct 5 ms 22520 KB Output is correct
8 Correct 7 ms 22352 KB Output is correct
9 Correct 5 ms 22260 KB Output is correct
10 Correct 5 ms 22352 KB Output is correct
11 Correct 6 ms 22352 KB Output is correct
12 Correct 5 ms 22352 KB Output is correct
13 Correct 6 ms 22352 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

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31168 KB Output is correct
2 Correct 64 ms 31120 KB Output is correct
3 Correct 60 ms 30536 KB Output is correct
4 Correct 56 ms 29592 KB Output is correct
5 Correct 51 ms 28496 KB Output is correct
6 Correct 50 ms 28036 KB Output is correct
7 Correct 47 ms 27728 KB Output is correct
8 Correct 40 ms 27208 KB Output is correct
9 Correct 50 ms 27176 KB Output is correct
10 Correct 37 ms 26976 KB Output is correct
11 Correct 35 ms 26904 KB Output is correct
12 Correct 36 ms 26952 KB Output is correct
13 Correct 39 ms 26824 KB Output is correct
14 Correct 39 ms 29776 KB Output is correct
15 Correct 59 ms 37056 KB Output is correct
16 Correct 57 ms 34936 KB Output is correct
17 Correct 65 ms 35728 KB Output is correct
18 Correct 56 ms 33732 KB Output is correct
19 Incorrect 46 ms 29776 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 20048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 20048 KB Output isn't correct
2 Halted 0 ms 0 KB -