Submission #52811

#	Time	Username	Problem	Language	Result	Execution time	Memory
52811		FLDutchman	Duathlon (APIO18_duathlon)	C++14	18 / 100	1082 ms	28344 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define int long long
#define MMAX 16384
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;

const ll INF = 1000000000000000000LL;
const int NMAX = 1e5+4;
const int mod = 1e9+7;
const ld eps = 1e-10;
const ld PI = acos(-1);

int N, M;

vi adj[NMAX];

vi idx, low, color;
stack<int> comp;
vi size;
int id, c;

int findBridges(int n, int p){
    idx[n] = low[n] = id++;
    comp.push(n);
    for(int k : adj[n]) if(k != p) {
        if(idx[k] == -1) low[n] = min(low[n],  findBridges(k, n) );
        else low[n] = min(low[n], idx[k]);
    }
    if(low[n] == idx[n]) {
        size.pb(1);
        while(comp.top() != n) {
            color[comp.top()] = c;
            comp.pop();
            size[c]++;
        }
        color[comp.top()] = c;
        comp.pop();
        c++;
    }
    return low[n];
}

vi tree[NMAX];
bitset<NMAX> vis;

void buildTree(int n){
    vis[n] = 1;
    for(int k : adj[n]){
        if(color[k] != color[n]) tree[color[k]].pb(color[n]);
        if(!vis[k]) buildTree(k);
    }
}

vi subSize[NMAX];
int dfs(int n, int p){
    int sum = size[n];
    for(int i = 0; i < tree[n].size(); i++) {
        int k = tree[n][i], &s = subSize[n][i];
        if(k == p) continue;
        if(s == -1) s = dfs(k, n);
        sum += s;
    }
    //cout << n << " " << p << " " << sum << endl;
    return sum;
}

int f(int n){
    int C = size[n];
    int S = 0;
    for(int t : subSize[n]) S += t;
    int sum = 0;
    for(int t : subSize[n]) sum += t*t;
    //cout << "f " << C << " " << S << " " << sum << endl;
    return C*(C-1)*(C-2)
         + 2*(C-1)*(C-1)*S
         + C*(S*S - sum);
}

signed main(){
    fast_io();
    c = 0;
    cin >> N >> M;
    FOR(i, 0, M){
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    idx.assign(N, -1); low.assign(N, INF);
    color.assign(N, -1);
    FOR(i, 0, N) if(idx[i] == -1) findBridges(i, -1);
    //FOR(i, 0, N)        cout << color[i] << endl;
    vis.reset();
    FOR(i, 0, N) if(!vis[i]) buildTree(i);

    //FOR(i, 0, c) for(int k : tree[i]) cout << i << " " << k << endl;
    FOR(i, 0, c) subSize[i].assign(tree[i].size(), -1);
    FOR(i, 0, c) dfs(i, -1);


    int sum = 0;
    FOR(i, 0, c) sum += f(i);
    cout << sum << endl;
}


/*
4 3
1 2
2 3
3 4


4 4
1 2
2 3
3 4
4 2


*/

Compilation message (stderr)

count_triplets.cpp: In function 'long long int dfs(long long int, long long int)':
count_triplets.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < tree[n].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~

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