Submission #572181

#	Time	Username	Problem	Language	Result	Execution time	Memory
572181		somo	Duathlon (APIO18_duathlon)	C++14	66 / 100	421 ms	89504 KiB

count_triplets

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll>
#define F first
#define S second
#define double long double
#define all(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;

const int MOD = 1e9 + 7 ;
const int  N= 5e5 + 10;
const ll INF= 1e18+10;

struct trp{ll F,S,T;};

ll po(ll x,ll y)
{
    ll ans = 1;
    while(y){
        if( y & 1 ) ans *=x;
        y /= 2;
        x *=x;
        //ans %= MOD;
        //x %= MOD;
    }
    return ans;
}

ll ans;
ll sz[N];
ll val[N];
ll ctr = 1;
ll node[N];
bool vis[N];
ll n , m, nn ;
vector<ll>v[N];
map<pii,bool>mp;
vector<ll>com[N];
ll tin[N],low[N];
vector<ll>tree1[N];
vector<ll>no_name[N];

void dfs_br(ll x,ll p)
{
    tin[x] = low[x] = ctr ++;
    for(auto i : v[x]){
        if(i == p) continue;
        if(!tin[i]){
            dfs_br(i,x);
            low[x] = min(low[x], low[i]);
            if(low[i] > tin[x]){
                mp[{x,i}] = 1;
                mp[{i,x}] = 1;
            }
        }
        else low[x] = min(low[x] , tin[i]);
    }
}

void dfs(ll x)
{
    com[ctr].pb(x);
    node[x] = ctr;
    val[ctr] ++;
    for(auto i : v[x]){
        if(mp[{x,i}]){
            if(node[i]){
                no_name[i].pb(node[x]);
                no_name[x].pb(node[i]);
                tree1[node[x]].pb(node[i]);
                tree1[node[i]].pb(node[x]);
            }
        }
        else{
            if(!node[i]) dfs(i);
        }
    }
}

void dfs_tr(ll x)
{
    vis[x] = 1;
    for(auto i : tree1[x]){
        if(!vis[i]){
            dfs_tr(i);
            sz[x] += sz[i];
        }
    }
    sz[x] += val[x];
}

void dfs_get(ll x)
{
    vis[x] = 1;
    if(val[x] >= 3) ans += val[x] * (val[x]-1) * (val[x]-2);
    ll curr = 0;
    ll h = (val[x] >= 2 ? (val[x]-1)*(val[x]-1) : 0);
    vector<ll>g;
    for(auto i : com[x]){
        ll sm = 0;
        for(auto j : no_name[i]){
            if(vis[j]) sm += nn-sz[x];
            else sm += sz[j];
        }
        if(sm) g.pb(sm);
    }

    if(g.size() > 1){
        ll sm = g[0];
        for(ll i= 1; i < g.size() ; i ++){
            curr += g[i] * sm;
            sm += g[i];
        }
        ans += curr*2*val[x];
    }

    for(auto i : com[x]){
        vector<ll>gg;
        for(auto j : no_name[i]){
            if(vis[j]) gg.pb(nn-sz[x]);
            else gg.pb(sz[j]);
        }
        if(gg.size() > 1){
            ll smm = gg[0];
            ll b = 0;
            for(ll j = 1 ; j < gg.size() ; j ++){
                b += gg[j] * smm;
                smm += gg[j];
            }
            ans += b * 2;
        }
    }

    for(auto i : tree1[x]){
        if(vis[i]){
            ans += h * (nn-sz[x]) * 2;
        }
        else{
            ans += h * sz[i] * 2;
            dfs_get(i);
        }
    }
}

void solve()
{
    cin >> n >> m;
    for(ll i= 1; i <= m; i ++){
        ll x,y;
        cin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    for(int  i= 1; i <= n; i ++){
        if(!tin[i]) dfs_br(i,i);
    }
    ctr = 1;
    for(ll i= 1; i <= n ; i ++){
        if(!node[i]) dfs(i),ctr ++;
    }
    ctr --;
    for(ll i= 1; i <= ctr; i ++){
        if(!vis[i]) dfs_tr(i);
    }
    for(ll i= 1; i <= ctr ; i ++) vis[i] = 0;
    for(ll i= 1; i <= ctr ; i ++){
        if(!vis[i]){
            nn = sz[i];
            dfs_get(i);
        }
    }
    cout << ans << endl;
}

int main(){
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen(".in" , "r" , stdin);freopen(".out" , "w" , stdout);
	int t = 1;
    //cin >> t;
	while(t--) {solve() ; }
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs_get(long long int)':
count_triplets.cpp:118:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(ll i= 1; i < g.size() ; i ++){
      |                      ~~^~~~~~~~~~
count_triplets.cpp:134:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             for(ll j = 1 ; j < gg.size() ; j ++){
      |                            ~~^~~~~~~~~~~

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