Submission #951608

#	Time	Username	Problem	Language	Result	Execution time	Memory
951608		Boycl07	Keys (IOI21_keys)	C++17	100 / 100	577 ms	57456 KiB

keys

#include "keys.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task ""
#define sz(a) int(a.size())
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}


struct DSU
{
    vector<int> par;
    vector<int> sz;

    void init(int n)
    {
        par.assign(n + 1, 0);
        sz.assign(n + 1, 0);
        FOR(i, n) par[i] = i, sz[i] = 1;
    }

    int find_set(int u) {return u == par[u] ? u : par[u] = find_set(par[u]);}
};

vector<int> find_reachable(vector<int> r, vector<int> u_, vector<int> v_, vector<int> c_)
{
    int n = sz(r), m = sz(c_);
    DSU dsu;
    dsu.init(n);
    vector<bool> ok(n, false);
    vector<vector<pii>> g(n);
    for(int i = 0; i < m; ++i)
    {
        int u = u_[i], v = v_[i], c = c_[i];
        g[u].pb({v, c});
        g[v].pb({u, c});
    }
    int Min = 1e9 + 1;
    vector<int> res;
    while(true)
    {
        bool flag = 0;

        vector<vector<int>> pot(n);
        vector<bool> vis(n, false);
        vector<bool> keys(n, false);
        vector<int> cur_keys;

        function<void(int)> bfs = [&](int s)
        {
            for(int x : cur_keys) keys[x] = 0, pot[x].clear();
            cur_keys.clear();
            queue<int> q;
            q.push(s);
            vis[s] = 1;
            vector<int> cur;
            int cnts = 0;
            while(sz(q))
            {
                ++cnts;
                int u = q.front(); q.pop();
                cur.pb(u);
                if(!keys[r[u]])
                {
                    keys[r[u]] = 1;
                    cur_keys.pb(r[u]);
                    for(int v : pot[r[u]])
                    {
                        int c = dsu.find_set(v);
                        if(c != s)
                        {
                            dsu.par[s] = c;
                            vis[c] = 1;
                            return;
                        }
                        if(vis[v]) continue;
                        vis[v] = 1;
                        q.push(v);
                    }
                    pot[r[u]].clear();
                }
                for(pii e : g[u])
                {
                    int v = e.fi, c = e.se;
                    if(!keys[c])
                    {
                        if(pot[c].empty()) cur_keys.pb(c);
                        pot[c].pb(v);
                    }
                    else
                    {
                        int c_ = dsu.find_set(v);
                        if(c_ != s)
                        {
                            dsu.par[s] = c_;
                            vis[c_] = 1;
                            return;
                        }
                        if(vis[v]) continue;
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
            ok[s] = 1;
                if(minimize(Min, sz(cur))) res = move(cur);
                else if(Min == sz(cur)) for(int x : cur) res.pb(x);
        };

        FOR(i, n) if(dsu.find_set(i) == i && !ok[i] && !vis[i])
            bfs(i), flag = 1;
        if(!flag) break;
    }

    vector<int> out(n, 0);
    for(int x : res) out[x] = 1;


	return out;
}

//int main() {
//    int n, m;
//    freopen("keys.inp", "r", stdin);
//    freopen("keys.out", "w", stdout);
//    assert(2 == scanf("%d%d", &n, &m));
//    std::vector<int> r(n), u(m), v(m), c(m);
//    for(int i=0; i<n; i++) {
//        assert(1 == scanf("%d", &r[i]));
//    }
//    for(int i=0; i<m; i++) {
//        assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
//    }
//    fclose(stdin);
//
//    std::vector<int> ans = find_reachable(r, u, v, c);
//
//    for (int i = 0; i < (int) ans.size(); ++i) {
//        if(i) putchar(' ');
//        putchar(ans[i]+'0');
//    }
//    printf("\n");
//    return 0;
//}

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