oj.uz

Submission #734043

# Submission time Handle Problem Language Result Execution time Memory
734043 2023-05-01T14:24:35 Z Ronin13 Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 74 ms 164704 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const int nmax = 1000001;

set <int> in[nmax], out[nmax];
set <int> indg[nmax];
ll sz[nmax];
ll curans;
int p[nmax];
vector <vector <int> > cmp(nmax);

int find_set(int a){
    return p[a] == a ? a : p[a] = find_set(p[a]);
}

void union_sets(int a, int b){
    if(a == b)
        return;
    if(sz[a] < sz[b])
        swap(a, b);

    curans -= (ll)indg[b].size() * sz[b];
    curans -= (ll)indg[a].size() * sz[a];
    curans -= sz[b] * sz[b] - sz[b];
    curans -= sz[a] * sz[a] - sz[a];
  //  cout << curans << ' ';

    vector <int> vec;
    out[b].erase(a);
    out[a].erase(b);
    in[a].erase(b);
    in[b].erase(a);
    for(int to : out[b]){
        if(find_set(to) == a) continue;
        if(in[a].find(to) != in[a].end())
            vec.pb(to);
        out[a].insert(to);
        in[to].erase(b);
        in[to].insert(a);
    }
    for(int to : in[b]){
        if(find_set(to) == a) continue;
        if(out[a].find(to) != out[a].end())
            vec.pb(to);
        in[a].insert(to);
        out[to].erase(b);
        out[to].insert(a);
    }
    for(int to : indg[b]){
       if(find_set(to) != a) indg[a].insert(to);
    }
    for(int to : cmp[b]){
        cmp[a].pb(to);
        indg[a].erase(to);
    }
    p[b] = a;
    sz[a] += sz[b];
    curans += sz[a] * (ll)indg[a].size();
    //cout << sz[a] << ' ';
  //  cout << curans << ' ';
    curans += sz[a] * sz[a] - sz[a];
    for(int to : vec){
        union_sets(a, to);
    }
}

void Merge(int a, int b){
    b = find_set(b);
    int x= find_set(a);
    //cout << x << ' ' << b << "\n";
    if(x == b)
        return;
    if(in[x].find(b) != in[x].end()){
      // cout << 1;
        union_sets(x, b);
    }
    else{
        curans -= sz[b] * (ll)indg[b].size();
        indg[b].insert(a);
        curans += sz[b] * (ll)indg[b].size();
        in[b].insert(x);
        out[x].insert(b);
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        p[i] = i;
        sz[i] = 1;
        cmp[i].pb(i);
    }
    int m; cin >> m;
    for(int i= 1; i <= m; i++){
        int u, v; cin >> u >> v;
        Merge(u, v);
        cout << curans << "\n";
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 164584 KB Output is correct
2 Correct 73 ms 164680 KB Output is correct
3 Correct 73 ms 164704 KB Output is correct
4 Correct 74 ms 164704 KB Output is correct
5 Correct 71 ms 164688 KB Output is correct
6 Correct 72 ms 164692 KB Output is correct
7 Incorrect 74 ms 164636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 164584 KB Output is correct
2 Correct 73 ms 164680 KB Output is correct
3 Correct 73 ms 164704 KB Output is correct
4 Correct 74 ms 164704 KB Output is correct
5 Correct 71 ms 164688 KB Output is correct
6 Correct 72 ms 164692 KB Output is correct
7 Incorrect 74 ms 164636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 164584 KB Output is correct
2 Correct 73 ms 164680 KB Output is correct
3 Correct 73 ms 164704 KB Output is correct
4 Correct 74 ms 164704 KB Output is correct
5 Correct 71 ms 164688 KB Output is correct
6 Correct 72 ms 164692 KB Output is correct
7 Incorrect 74 ms 164636 KB Output isn't correct
8 Halted 0 ms 0 KB -