Submission #211933

#	Time	Username	Problem	Language	Result	Execution time	Memory
211933		3zp	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1862 ms	123556 KiB

joitter2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,ll> f[300009];
map<ll,ll> g[300009];
ll p[300009],s[300009];
int br[309][309];
ll ans;
ll P(ll x){
    if(x == p[x]) return x;
    p[x] = P(p[x]);
    return p[x];
}
void un(ll x, ll y){
    x = P(x); y = P(y);
    if(x == y ) return;
    if(f[x].size() + g[x].size() >
       f[y].size() + g[y].size()) 
      swap(x, y);
    ans -= s[x] * (ll)f[x].size() - s[x];
    ans -= s[y] * (ll)f[y].size() - s[y];
    s[y] += s[x];
    p[x] = y;
    vector<int> v;
    for(auto it = f[x].begin(); it != f[x].end(); it++){
        f[y][it->first]=1;
        int u = P(it->first);
        if(g[y].find(u) != g[y].end()) 
          v.push_back(it->first);
        g[u][y] = 1;
        if(g[u].find(x) != g[u].end()) 
          g[u].erase(g[u].find(x));
    }
    for(auto it = g[x].begin(); it != g[x].end(); it++){
        g[y][it->first] = 1;
        if(g[it->first].find(y) != g[it->first].end()) 
          v.push_back(it->first);
    }
    ans += s[y] * (ll)f[y].size() - s[y];
    for(int u : v)
        un(y, u);
}
main(){
    ll n, q;
    cin >> n >> q;
    for(ll i = 1; i <= n; i++)
        s[i] = 1, p[i] = i, f[i][i] = 1;
    while(q--){
        ll a, b;
        cin >> a >> b;
        ll c = P(b), d = P(a);
        if(f[c].find(a) == f[c].end()){
            if(g[c].find(d) != g[c].end()) un(a, b);
            else{
                f[c][a] = 1,
                ans += s[c];
            }
            g[P(a)][c] = 1;
        }
        cout<<ans<<endl;
    }
}

Compilation message (stderr)

joitter2.cpp:43:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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