Submission #212017

#	Time	Username	Problem	Language	Result	Execution time	Memory
212017		Mercenary	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	686 ms	50800 KiB

joitter2

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int n , m;
ll res = 0;

int lab[maxn];
set<int> in[maxn],out[maxn];
vector<int> node[maxn];
int FindLab(int u){return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);}
void Merge(int u , int v){
    u = FindLab(u);v = FindLab(v);
    if(u == v)return;
    res -= (ll)in[u].size() * node[u].size();
    res -= (ll)in[v].size() * node[v].size();
    res -= (ll)node[u].size() * ((int)node[u].size() - 1);
    res -= (ll)node[v].size() * ((int)node[v].size() - 1);
    if(in[u].size() + out[u].size() + node[u].size() < in[v].size() + out[v].size() + node[v].size())
        swap(u , v);
    lab[u] += lab[v];
    lab[v] = u;
    for(auto & c : node[v]){
        node[u].pb(c);
        in[u].erase(c);
    }
    vector<int> add;
    for(auto & c : in[v]){
        if(FindLab(c) != u){
            out[FindLab(c)].erase(v);
            out[FindLab(c)].insert(u);
            in[u].insert(c);
            if(out[u].find(FindLab(c)) != out[u].end()){
                add.pb(c);
            }
        }
    }
    for(auto & c : out[v]){
        if(FindLab(c) != u){
            out[u].insert(c);
            if(out[c].find(u) != out[c].end()){
                add.pb(c);;
            }
        }
    }
    out[u].erase(v);
    res += (ll)in[u].size() * node[u].size();
    res += (ll)node[u].size() * ((int)node[u].size() - 1);
    for(auto c : add){
        Merge(u,c);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i){
        lab[i] = -1;node[i].pb(i);
    }
    for(int i = 1 ; i <= m ; ++i){
        int u , v;cin >> u >> v;
        if(FindLab(u) != FindLab(v)){
            if(out[FindLab(v)].find(FindLab(u)) != out[FindLab(v)].end()){
                Merge(u,v);
            }else if(in[FindLab(v)].find(u) == in[FindLab(v)].end()){
                in[FindLab(v)].insert(u);
                res += node[FindLab(v)].size();
                out[FindLab(u)].insert(FindLab(v));
            }
        }
        cout << res << '\n';
    }
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:73:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:74:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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