제출 #571781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571781		somo	철인 이종 경기 (APIO18_duathlon)	C++14	31 / 100	359 ms	55928 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;
ll tin[N],low[N];
vector<ll>tree1[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)
{
    node[x] = ctr;
    val[ctr] ++;
    for(auto i : v[x]){
        if(mp[{x,i}]){
            if(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 : tree1[x]){
        if(vis[i]){
            g.pb(nn-sz[x]);
            ans += h * (nn-sz[x]) * 2;
        }
        else{
            ans += h * sz[i] * 2;
            dfs_get(i);
            g.pb(sz[i]);
        }
    }
    if(g.size()){
        ll sm = g[0];
        for(ll i= 1; i < g.size() ; i ++){
            curr += g[i] * sm;
            sm += g[i];
        }
    }
    if(tree1[x].size() > 1) ans += curr*2*val[x];
}

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() ; }
}

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp: In function 'void dfs_get(long long int)':
count_triplets.cpp:115: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]
  115 |         for(ll i= 1; i < g.size() ; i ++){
      |                      ~~^~~~~~~~~~

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