Submission #752656

#	Time	Username	Problem	Language	Result	Execution time	Memory
752656		Ronin13	Keys (IOI21_keys)	C++17	100 / 100	1296 ms	207852 KiB

keys

#include <vector>
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 500001;
int p[nmax][2];
int sz[nmax][2];

void make_set(int v, int ind){
    p[v][ind] = v;
    sz[v][ind] = 1;
}

int find_set(int v, int ind){
    if(p[v][ind] == v){
        return v;
    }
    return p[v][ind] = find_set(p[v][ind], ind);
}

void union_sets(int a, int b, int ind){
     a = find_set(a, ind);
     b = find_set(b, ind);
     if(a == b)
        return;
     p[b][ind] = a;
     sz[a][ind] += sz[b][ind];
}
vector <pii> empt;
struct node{

    map <int,int>mp;
    set <int> st;
    vector <vector <pii> > edg;

    int tot = 0;
    int sz;
    int p;
    node(){
    }
    node(int x){
        sz = 1;
        p = x;
        tot = 0;
        edg.pb(empt);
    }
    void add_edge(int x, int c){
        tot++;
        if(!mp[c]){
            mp[c] = edg.size();
            edg.pb(empt);
        }
        edg[mp[c]].pb({x, c});
    }
    void add_color(int x){
        st.insert(x);
    }
    int get_edge(int v){
        while(!st.empty()){
            int x = *st.begin();
            int o = mp[x];
            if(!o) {st.erase(st.begin());continue;}
            while(!edg[o].empty()){
                int u = edg[o].back().f;
                edg[o].pop_back();
                if(find_set(u, 1) != find_set(v, 1)){
                    return u;
                }
            }
            st.erase(st.begin());
        }
        return -1;
    }
}vert[nmax];

void merg(int u, int v){
    u = find_set(u, 1);
    v = find_set(v, 1);
    if(vert[v].tot > vert[u].tot){
        swap(vert[u].edg, vert[v].edg);
        swap(vert[u].tot, vert[v].tot);
        swap(vert[u].mp, vert[v].mp);
        swap(vert[u].st, vert[v].st);
    }
    for(auto x : vert[v].edg){
        for(auto to : x){
            vert[u].add_edge(to.f, to.s);
        }
    }
    for(auto x : vert[v].st){
        vert[u].st.insert(x);
    }
    union_sets(u, v, 1);
}

set <int> roots;
int ans = 1e9;
set <int> good;
bool upd(){
    if(roots.empty()){
        return false;
    }
    while(!roots.empty()){
        int x = *roots.begin();
        int val = vert[x].get_edge(x);
        if(val == -1){
            if(sz[x][1] < ans){
                good.clear();
                ans = sz[x][1];
                good.insert(x);
            }
            else if(sz[x][1] == ans){
                good.insert(x);
            }
            roots.erase(roots.begin());
        }
        else{
            if(find_set(x, 0) == find_set(val , 0)){
                while(find_set(val, 1) != find_set(x, 1)){
                    int xx = find_set(val, 1);
                    merg(x, val);
                    val = vert[xx].p;
                }

            }
            else{
                roots.erase(roots.begin());
                vert[x].p = val;
                union_sets(val, x, 0);
            }
            return true;
        }

    }
    return false;
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = r.size();
	for(int i = 0; i < n; i++){
        vert[i] = {i};
        vert[i].add_color(r[i]);
        make_set(i, 0);
        make_set(i, 1);

	}
	for(int i = 0; i < u.size(); i++){
        vert[u[i]].add_edge(v[i], c[i]);
        vert[v[i]].add_edge(u[i], c[i]);
	}
	for(int i = 0; i < n; ++i)
        roots.insert(i);
	while(upd()){}
	vector <int> ans(n);
	for(int i = 0; i < n; ++i){
        if(good.find(find_set(i, 1)) != good.end())
            ans[i] = 1;
	}
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:155:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33