Submission #752526

#	Time	Username	Problem	Language	Result	Execution time	Memory
752526		1bin	Keys (IOI21_keys)	C++17	100 / 100	1121 ms	158908 KiB

keys

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
int n, m, par[NMAX], dfsn[NMAX], fin[NMAX], sz[NMAX], bad[NMAX], t, from[NMAX];
vector<int> E[NMAX];
set<int> K[NMAX];
map<int, vector<int>> mp[NMAX];
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}

void Union(int a, int b){
    if(K[a].size() + mp[a].size() < K[b].size() + mp[b].size()) swap(K[a], K[b]), swap(mp[a], mp[b]);
    for(auto&[k, v] : mp[b]){
        if(K[a].find(k) == K[a].end()) {
            if(mp[a][k].size() < v.size()) swap(mp[a][k], v);
            for(auto&y : v) mp[a][k].emplace_back(y);
        }
        else{
            if(E[a].size() < v.size()) swap(E[a], v);
            for(auto& y : v) E[a].emplace_back(y);
        }
    }
    for(auto& k : K[b]) {
        K[a].emplace(k);
        for(int& y : mp[a][k]) E[a].emplace_back(y);
        mp[a].erase(k);
    }
    
    if(E[a].size() < E[b].size()) swap(E[a], E[b]);
    for(auto& e : E[b]) E[a].emplace_back(e);
    E[b].clear();
    
    sz[a] += sz[b];
    par[b] = a;
    bad[a] |= bad[b];
    return;
}

void dfs(int x){
    dfsn[x] = ++t;
    
    while(E[x].size()){
        x = find(x);
        int nx = find(E[x].back()); E[x].pop_back();
        if(x == nx) continue;
        
        if(!dfsn[nx]){
            from[nx] = x;
            dfs(nx);
        }
        else if(!fin[nx]){
            for(int i = x; i != nx; i = from[i]) Union(nx, i);
        }
        
        if(find(nx) != find(x)) bad[x] = 1;
    }
    fin[x] = 1;
    return;
}

vector<int> find_reachable(vector<int>r, vector<int> u, vector<int> v, vector<int> c){
    n = r.size(); m = u.size();
    auto add_edge = [&](int& a, int& b, int& c){
        if(r[a] == c) E[a].emplace_back(b);
        else mp[a][c].emplace_back(b);
    };
    for(int i = 0; i < m; i++){
        add_edge(u[i], v[i], c[i]);
        add_edge(v[i], u[i], c[i]);
    }
    
    memset(par, -1, sizeof(par));
    for(int i = 0; i < n; i++) sz[i] = 1, K[i].emplace(r[i]);
    for(int i = 0; i < n; i++)
        if(!dfsn[i]) dfs(i);
    
    vector<int> res(n, 0);
    int mn = n + 1;
    for(int i = 0; i < n; i++) if(!bad[find(i)]) mn = min(mn, sz[find(i)]);
    for(int i = 0; i < n; i++) if(!bad[find(i)] && sz[find(i)] == mn) res[i] = 1;
    return res;
}

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<int> r(n), u(m), v(m), c(m);
    for(auto& i : r) cin >> i;
    for(auto& i : u) cin >> i;
    for(auto& i : v) cin >> i;
    for(auto& i : c) cin >> i;
    
    vector<int> res = find_reachable(r, u, v, c);
    for(int i = 0; i < n; i++) cout << res[i] << ' ';
    return 0;
}
*/

/*
test1
4 5
0 1 1 2
0 0 1 1 3
1 2 2 3 1
0 0 1 0 2

test2
7 10
0 1 1 2 2 1 2
0 0 1 1 2 3 3 4 4 5
1 2 2 3 3 4 5 5 6 6
0 0 1 0 0 1 2 0 2 1

test3
3 1
0 0 0
0 1 0
*/

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