Submission #593758

#	Time	Username	Problem	Language	Result	Execution time	Memory
593758		MadokaMagicaFan	Keys (IOI21_keys)	C++17	0 / 100	113 ms	211672 KiB

keys

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)(v).size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second
/* #define ONPC */

using vi = vector<int>;
using pi = array<int,2>;

const int N = 3e5;

int st[N+1];
int us[N];
int p[N+1];
int ch[N+1];
int d[N+1];

/* deque<int> q[N]; */
/* set<int> s[N]; */

int s[N];
vi adj[N][30];


int
getp(int x)
{
    return p[x] = (x == p[x]) ? x : getp(p[x]);
}

int
dfs(int x)
{
    if (st[x]&1) return p[x];
    st[x] |= 1;

    int lc = 1, u;

    while (lc) {
        lc = 0;
        for (int i = 0; i < 30; ++i) {
            if ((s[x]>>i)&1) {
                while (sz(adj[x][i])) {
                    u = adj[x][i].back();
                    u = getp(u);
                    adj[x][i].pop_back();

                    if (!(st[u]&1)) {
                        d[u] = d[x]+1;
                        dfs(u);
                        ch[x] += ch[u];
                        if (d[getp(x)] > d[getp(u)]) {
                            p[x] = getp(u);
                            i = 31;
                            lc = 0;
                            break;
                        }
                        lc = 1;
                    } else if (st[u]&2) {
                        p[x] = N;
                        i = 31;
                        lc = 0;
                        break;
                    } else {
                        p[x] = getp(u);
                        i = 31;
                        lc = 0;
                        break;
                    }
                }
            }
        }
    }

    st[x] |= 2;

    /* Check if useless */
    if (p[x] == N)
        return p[x];

    /* Check if has bigger parrent */
    if (getp(x) != x) {
        /* Push all values */
        int u = getp(x);
        s[u] |= s[x];
        for (int i = 0; i < 30; ++i) {
            if (sz(adj[x][i]) > sz(adj[u][i]))
                swap(adj[x][i], adj[u][i]);

            while (sz(adj[x][i])) {
                adj[u][i].pb(adj[x][i].back());
                adj[x][i].pop_back();
            }
        }
    }


    return p[x];
}

vi
find_reachable(vi r, vi u, vi v, vi c)
{
    vi ans;
    int n, m;

    n = sz(r);
    m = sz(u);
    ans.assign(n,0);

    p[N] = N;
    ch[N] = N+1;
    d[N] = -1;

    for (int i = 0; i < n; ++i) {
        p[i] = i;
        ch[i] = 1;
        d[i] = 0;
        s[i] = 1<<(r[i]);
        /* s[i].insert(r[i]); */
    }

    for (int i = 0; i < m; ++i) {
        /* q[u[i]].pb(i); */
        assert(c[i] < 30);
        adj[u[i]][c[i]].pb(v[i]);
        adj[v[i]][c[i]].pb(u[i]);
    }

    for (int i = 0; i < n; ++i) {
        if (st[i] == 0)
            dfs(i);
    }

    int mnv = N+2;

    for (int i = 0; i < n; ++i) {
        mnv = min(mnv,ch[getp(i)]);
    }


    for (int i = 0; i < n; ++i) {
        if (ch[getp(i)] == mnv)
            ans[i] = 1;
    }


    return ans;
}

#ifdef INTER
#endif

#ifdef ONPC
void
solve()
{
    int _n, _m;
    cin >> _n >> _m;

    cout << _n << ' ' << _m << endl;

    vector<int> r(_n);
    for (int i = 0; i < _n; ++i)
        cin >> r[i];
    
    vector<int> u(_m), v(_m), c(_m);
    for (int i = 0; i < _m; ++i)
        cin >> u[i] >> v[i] >> c[i];

    vi ans = find_reachable(r, u, v, c);

    for (auto u : ans) {
        cout << u << ' ';
    }
    cout << endl;
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

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