Submission #1114757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1114757	2024-11-19T14:36:46 Z	asli_bg	Duathlon (APIO18_duathlon)	C++11	0 / 100	66 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;
            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	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

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

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

#	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	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

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

#	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	-

Submission #1114757

Compilation message