Submission #59321

#	Time	Username	Problem	Language	Result	Execution time	Memory
59321		wjoao	Duathlon (APIO18_duathlon)	C++11	25 / 100	54 ms	1736 KiB

count_triplets

#include<bits/stdc++.h>
#define maxn 10010
#define ll long long

using namespace std;

vector<ll> g[maxn];
ll n, m, a, b, t=1, tempo_atual, tempo[maxn], sol, grupo[maxn], filhos[maxn], filhos_fora_grupo[maxn], filhos_grupo[maxn], mark[maxn];


void dfs(int v, int p){
    tempo[v] = tempo_atual++;

    int grupo_achado = 0;

    filhos[v] = 1;
    filhos_fora_grupo[v] = 1;

    for(int i = 0; i < g[v].size(); i++){
        int u = g[v][i];

        if( u == p ) continue;

        if( tempo[u] > 0 && grupo[u] != 0 && tempo[u] < tempo[v] ){
            grupo_achado = grupo[u];
            continue;
        }
        if( tempo[u] > 0 ) continue;

        dfs(u, v);
        if( grupo[u] ){
            grupo_achado = grupo[u];
        }else{
            filhos_fora_grupo[v] += filhos[u];
        }
        filhos[v] += filhos[u];
    }
    grupo[v] = grupo_achado;
}

void solve_group(int v, int _grupo){
    mark[v] = true;

    for(int i = 0; i < g[v].size(); i++){
        int u = g[v][i];

        if(mark[u]) continue;

        if(grupo[u] == _grupo){
            solve_group(u, _grupo);
        }
    }
    // cout << "solve_group v: " << v << " QUantidade de filhos do grupo " << filhos_grupo[_grupo] << " filhos fora do grupo: " <<  filhos_fora_grupo[v] << endl;
    sol += (filhos_grupo[_grupo]-filhos_fora_grupo[v])*filhos_fora_grupo[v];
}

void solve_c(int c){
    // cout << endl << endl << "===> SOLVE: " << c << endl;
    memset(tempo, 0, sizeof tempo);
    memset(grupo, 0, sizeof grupo);

    tempo_atual = 1;
    tempo[c] = tempo_atual++;
    int grupo_atual = 0;
    filhos[c] = 0;

    vector<int> componentes;
    for(int i = 0; i < g[c].size(); i++){
        int u = g[c][i];
        if(grupo[u] != 0) continue;
        grupo[c] = ++grupo_atual;
        componentes.push_back(u);
        dfs(u, c);
        // cout << "Filhos de " << u << " são " << filhos[u] << endl;
        filhos_grupo[grupo_atual] = filhos[u];
        filhos[c] += filhos[u];
    }
    for(int i = 0; i < g[c].size(); i++){
        int u = g[c][i];
        // cout << "Grupo u: " << u << " é " << grupo[u] << endl;
    }
    // cout << "Raiz " << c << " Tem " << filhos[c] << " Filhos " << endl;
    for(int i = 0; i < componentes.size(); i++ ){
        int u = componentes[i];
        // cout << "Componente u: " << u << " Com filhos: " << filhos[u] << endl;
        sol += (filhos[c]-filhos[u])*filhos[u];
        if(grupo[u] != 0){
            memset(mark, 0, sizeof mark);
            mark[c] = true;
            solve_group(u, grupo[u]);
        }
    }
}


int main(){
    scanf(" %lld %lld", &n, &m);

    for(int i = 0; i < m; i++){
        scanf(" %lld %lld", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 1; i <= n; i++){
        solve_c(i);
        // cout << "i: " << i << " Sol após i: " << sol << endl;
    }
    printf("%lld\n", sol);
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < g[v].size(); i++){
                    ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void solve_group(int, int)':
count_triplets.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < g[v].size(); i++){
                    ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void solve_c(int)':
count_triplets.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < g[c].size(); i++){
                    ~~^~~~~~~~~~~~~
count_triplets.cpp:78:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < g[c].size(); i++){
                    ~~^~~~~~~~~~~~~
count_triplets.cpp:79:13: warning: unused variable 'u' [-Wunused-variable]
         int u = g[c][i];
             ^
count_triplets.cpp:83:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < componentes.size(); i++ ){
                    ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %lld %lld", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %lld %lld", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 15 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10