Submission #1114761

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1114761	2024-11-19T14:42:02 Z	asli_bg	Duathlon (APIO18_duathlon)	C++11	0 / 100	99 ms	47976 KB

count_triplets

#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

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

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

Subtask #9
0 / 10.0

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

Submission #1114761

Compilation message