Submission #1052589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052589		doducanh	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	558 ms	80472 KiB

joitter2

///breaker
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
const int maxn=1e5+7;
int r[maxn];
int sz[maxn];
set<int>child[maxn],adj[maxn],radj[maxn];
queue<ii>q;
ll ans=0;
int n,t;
void insert_weak_connection(int x,int y)
{
    adj[x].insert(y);
    radj[y].insert(x);
    if(adj[y].count(x)){
        q.push({x,y});
    }
}
int Find(int u)
{
    return (u==r[u])?u:r[u]=Find(r[u]);
}
int dsu_size(int u)
{
    return adj[u].size()+child[u].size()+radj[u].size();
}
void Union(int a,int b)
{
    if(a==b)return;
    if(dsu_size(a)<dsu_size(b))swap(a,b);
    ans+=(1ll*sz[a]*child[b].size()+1ll*sz[b]*child[a].size());
    sz[a]+=sz[b];
    r[b]=a;
    for(int i:child[b]){
        if(child[a].count(i))ans-=sz[a];
        else child[a].insert(i);
    }
    for(int i:adj[b]){
        radj[i].erase(b);
        insert_weak_connection(a,i);
    }
    for(int i:radj[b]){
        adj[i].erase(b);
        insert_weak_connection(i,a);
    }
}
void sol(){
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        r[i]=i;
        sz[i]=1;
        child[i].insert(i);
    }
    while(t--){
        int x,y;
        cin>>x>>y;
        y=Find(y);
        if(Find(x)!=y&&!child[y].count(x)){
            child[y].insert(x);
            ans+=sz[y];
            insert_weak_connection(Find(x),y);
            while(q.size()){
                auto[x,y]=q.front();
                q.pop();
                Union(Find(x),Find(y));
            }
        }
        cout<<ans<<"\n";
    }
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

joitter2.cpp: In function 'void sol()':
joitter2.cpp:71:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |                 auto[x,y]=q.front();
      |                     ^
joitter2.cpp: At global scope:
joitter2.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main()
      | ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83