Submission #736134

#	Time	Username	Problem	Language	Result	Execution time	Memory
736134		keta_tsimakuridze	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1152 ms	63544 KiB

joitter2

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, ans = 0, p[N], sz[N];
multiset<int> out[N];
set<pair<int,int>> in[N];
void _(int x, int y) {
    if(out[x].find(y) != out[x].end()) out[x].erase(y);
    while(in[y].upper_bound({x, 0}) != in[y].end() && (*in[y].upper_bound({x, 0})).f == x) {
        pii p = *in[y].upper_bound({x, 0});
        in[y].erase(p);
        ans -= sz[y];
    }
}
int find(int x) {
    return (p[x] == x ? p[x] : p[x] = find(p[x]));
}
void merge(int u, int v) {
    int U = find(u), V = find(v);
    if(U == V) return;
    _(U, V);
    _(V, U);
    if((int)in[U].size() + (int)out[U].size() < (int)in[V].size() + (int)out[V].size()) swap(U, V);
    p[V] = U;
    ans += sz[U] * sz[V] * 2;
    sz[U] += sz[V];
    ans += (int)in[U].size() * sz[V];
    vector<int> nbx;
    while(out[V].size()) {
        int x = *out[V].begin();
        out[V].erase(out[V].find(x));
        out[U].insert(x);
        pii p = *in[x].upper_bound({V, 0});
        in[x].erase(p); p.f = U; in[x].insert(p);
        if(out[x].find(U) != out[x].end()) nbx.push_back(x);
    }
    while(in[V].size()) {
        pii p = *in[V].begin();
        int x = p.f;
        out[x].erase(out[x].find(V));
        in[V].erase(p);
        if(in[U].find(p) == in[U].end()) ans += (sz[U] - sz[V]), out[x].insert(U);
        else ans -= sz[V];
        in[U].insert(p);
        if(out[U].find(x) != out[U].end()) nbx.push_back(x);

    }
    for(int i = 0; i < nbx.size(); i++) {
        int x = nbx[i];
        while(out[x].find(u) != out[x].end()) {
            out[x].erase(out[x].find(u));
            in[u].erase(*in[u].upper_bound({x, 0}));
            ans -= sz[u];
        }
        while(out[u].find(x) != out[u].end()) {
            out[u].erase(out[u].find(x));
            in[x].erase(*in[x].upper_bound({u, 0}));
            ans -= sz[x];
        }
    }
    for(int i = 0; i < nbx.size(); i++) merge(U, nbx[i]);
}
main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        int U = find(u), V = find(v);
        if(out[V].find(U) != out[V].end() || U == V) merge(u, v);
        else
        if(in[V].find({U, u}) == in[V].end()) ans += sz[V], out[U].insert(V), in[V].insert({U, u});
        cout << ans << endl;
    }
 }

Compilation message (stderr)

joitter2.cpp: In function 'void merge(long long int, long long int)':
joitter2.cpp:52:22: 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]
   52 |     for(int i = 0; i < nbx.size(); i++) {
      |                    ~~^~~~~~~~~~~~
joitter2.cpp:65:22: 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]
   65 |     for(int i = 0; i < nbx.size(); i++) merge(U, nbx[i]);
      |                    ~~^~~~~~~~~~~~
joitter2.cpp: At global scope:
joitter2.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main(){
      | ^~~~

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