제출 #558724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558724		jlallas384	열쇠 (IOI21_keys)	C++17	37 / 100	3041 ms	30064 KiB

keys

#include <bits/stdc++.h>
using namespace std;

struct ufds{
    vector<int> sz,par;
    ufds(int n): sz(n, 1),par(n){
        iota(par.begin(), par.end(), 0);
    }
    int find(int a){
        return par[a] == a ? a : par[a] = find(par[a]);
    }
    int unite(int a,int b){
        a = find(a), b = find(b);
        if(a == b) return 0;
        if(sz[a] < sz[b]) swap(a,b);
        sz[a] += sz[b];
        par[b] = a;
        return 1;
    }
    int same(int a,int b){
        return find(a) == find(b);
    }
};

vector<int> find_reachable(vector<int> r, vector<int> uv1, vector<int> uv2, vector<int> c) {
	vector<int> ans(r.size(), 1);
    int n = r.size();
    int m = uv1.size();
    vector<vector<pair<int,int>>> types(n);
    for(int i = 0; i < m; i++){
        types[c[i]].emplace_back(uv1[i], uv2[i]);
    }
    vector<int> vals(n);
    for(int st = 0; st < n; st++){
        vector<int> used(n);
        vector<vector<int>> g(n);
        queue<int> q;
        q.push(st);
        ufds ds(n);
        while(q.size()){
            int v = q.front(); q.pop();
            if(!used[r[v]]){
                for(auto &[i,j]: types[r[v]]){
                    if(ds.same(i,j)) continue;
                    if(ds.find(j) == ds.find(st)) swap(i,j);
                    if(ds.find(i) == ds.find(st)){
                        function <void(int,int)> dfs = [&](int cur,int p){
                            q.push(cur);
                            for(int u: g[cur]) if(u != p){
                                dfs(u, cur);
                            }
                        };
                        dfs(j,-1);
                    }
                    ds.unite(i,j);
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
                used[r[v]] = 1;
            }
        }
        vals[st] = ds.sz[ds.find(st)];
    }
    int mn = *min_element(vals.begin(), vals.end());
    for(int i = 0; i < n; i++){
        ans[i] = vals[i] == mn;
    }
	return ans;
}

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