Submission #1114759

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1114759	2024-11-19T14:39:50 Z	asli_bg	Duathlon (APIO18_duathlon)	C++11	0 / 100	70 ms	40640 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=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;
            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	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	5 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	48 ms	37952 KB	Output is correct
2	Correct	48 ms	38064 KB	Output is correct
3	Incorrect	52 ms	35908 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	4 ms	22352 KB	Output is correct
3	Correct	5 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	5 ms	22352 KB	Output is correct
7	Correct	5 ms	22352 KB	Output is correct
8	Correct	6 ms	22352 KB	Output is correct
9	Correct	5 ms	22352 KB	Output is correct
10	Incorrect	5 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	47 ms	31048 KB	Output is correct
2	Correct	51 ms	31048 KB	Output is correct
3	Correct	53 ms	31048 KB	Output is correct
4	Correct	54 ms	31048 KB	Output is correct
5	Correct	50 ms	31048 KB	Output is correct
6	Correct	70 ms	40640 KB	Output is correct
7	Correct	64 ms	37312 KB	Output is correct
8	Correct	60 ms	35780 KB	Output is correct
9	Correct	55 ms	34156 KB	Output is correct
10	Incorrect	54 ms	31196 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	5 ms	22524 KB	Output is correct
4	Correct	6 ms	22372 KB	Output is correct
5	Correct	5 ms	22352 KB	Output is correct
6	Correct	5 ms	22164 KB	Output is correct
7	Correct	5 ms	22352 KB	Output is correct
8	Correct	5 ms	22368 KB	Output is correct
9	Correct	5 ms	22516 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	22364 KB	Output is correct
14	Correct	5 ms	22520 KB	Output is correct
15	Correct	4 ms	22352 KB	Output is correct
16	Incorrect	4 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	44 ms	31116 KB	Output is correct
2	Correct	46 ms	31152 KB	Output is correct
3	Correct	56 ms	30536 KB	Output is correct
4	Correct	55 ms	29664 KB	Output is correct
5	Correct	45 ms	28496 KB	Output is correct
6	Correct	38 ms	27856 KB	Output is correct
7	Correct	36 ms	27720 KB	Output is correct
8	Correct	39 ms	27228 KB	Output is correct
9	Correct	34 ms	27208 KB	Output is correct
10	Correct	35 ms	26960 KB	Output is correct
11	Correct	31 ms	26960 KB	Output is correct
12	Correct	31 ms	26960 KB	Output is correct
13	Correct	33 ms	26960 KB	Output is correct
14	Correct	40 ms	29628 KB	Output is correct
15	Correct	56 ms	37060 KB	Output is correct
16	Correct	61 ms	35064 KB	Output is correct
17	Correct	61 ms	35784 KB	Output is correct
18	Correct	62 ms	33748 KB	Output is correct
19	Incorrect	60 ms	29768 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	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	5 ms	20048 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Submission #1114759

Compilation message