Submission #827931

#	Time	Username	Problem	Language	Result	Execution time	Memory
827931		Liudas	Keys (IOI21_keys)	C++17	100 / 100	466 ms	106684 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define ar array

using namespace std;

typedef long long ll;

using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;

const ll INF = 2e18;

struct EzArray {
    vector<int> a;
    int n;
    int T;
    EzArray(int sz = 0) : n(sz), T(1), a() {
        a.resize(n);
    }

    void upd(int x) {
        a[x] = T;
    }

    void clear() {
        T++;
    }

    int get(int i) {
        return a[i] == T;
    }

    vi get() {
        rep(i, n) a[i] = (a[i] == T);
        return a;
    }
};

vi find_reachable(vi r, vi U, vi V, vi c) {
    int n = r.size();
    int m = U.size();
    vector<vi> g(n);
    bool ok = false;
    rep(i, m) {
        g[U[i]].push_back(i);
        g[V[i]].push_back(i);
    }
    EzArray ans(n);
    int ANS = n + 1;
    auto get_size = [&] (int start) {
        vi was(n);
        vector<vector<int>> to(n);
        queue<int> q;
        q.push(start);
        vi used(n);
        used[start] = 1;
        int answer = 0;
        while(!q.empty()) {
            int v = q.front();
            q.pop();
            answer++;
            if (!was[r[v]]) {
                was[r[v]] = 1;
                for(auto u : to[r[v]]) {
                    if (!used[u]) {
                        used[u] = 1;
                        q.push(u);
                    }
                }
            }
            for(auto i : g[v]) {
                int u = U[i] ^ V[i] ^ v;
                if (used[u]) continue;
                if (was[c[i]]) {
                    q.push(u);
                    used[u] = 1;
                }  else {
                    to[c[i]].push_back(u);
                }
            }
        }
        if (ANS > answer) {
            ANS = answer;
            ans.clear();
        }
        if (ANS == answer) {
            rep(i, n) if (used[i]) ans.upd(i);
        }
        return answer;
    };
    vi comp(n);
    iota(all(comp), 0);
    int sz = n;
    vector<vi> toc(n);
    rep(i, n) toc[i].push_back(i);
    EzArray have_col(n);
    int K = sqrt(n);
    vi ban(n);
    while(sz > 0) {
        vvi g2(sz), gr2(sz);
        vi ban2(sz);
        rep(v, sz) {
            have_col.clear();
            for(auto i : toc[v]) have_col.upd(r[i]);
            for(auto i : toc[v]) {
                for(auto edge : g[i]) {
                    int j = U[edge] ^ V[edge] ^ i;
                    if (!have_col.get(c[edge])) continue;
                    if (ban[j]) {
                        ban2[v] = 1;
                        continue;
                    }
                    if (comp[j] == comp[i]) continue;
                    g2[comp[i]].push_back(comp[j]);
                    gr2[comp[j]].push_back(comp[i]);
                }
            } 
            if (toc[v].size() > ANS || ban2[v]) {
                ban2[v] = 1;
                continue;
            }
            if (g2[v].empty()) {
                ban2[v] = 1;
                if (toc[v].size() < ANS) {
                    ans.clear();
                    ANS = toc[v].size();
                }
                for(auto i : toc[v]) ans.upd(i);
            }
        }
        vi used(sz);
        vi ts;
        function<void(int)> dfs1 = [&] (int v) {
            used[v] = 1;
            for(auto u : gr2[v]) {                
                if (used[u]) continue;
                dfs1(u);
            }
            ts.push_back(v);
        };
        function<void(int)> dfs_ban = [&] (int v) {
            ban2[v] = 1;
            for(auto u : gr2[v]) {
                if (ban2[u] == 1) continue;
                dfs_ban(u);
            }
        };
        rep(i, sz) {
            if (ban2[i]) {
                dfs_ban(i);
            }
        }
        rep(i, sz) {
            if (ban2[i]) {
                used[i] = 1;
                for(auto j : toc[i]) ban[j] = 1;
            }
        }
        rep(i, sz) {
            if (used[i]) continue;
            dfs1(i);
        }
        vi comp2(sz, -1);
        //vi cnt(sz, 0);
        reverse(all(ts));
        function<void(int)> dfs2 = [&] (int v) {
            //cnt[comp2[v]]++;
            for(auto u : g2[v]) {
                if (comp2[u] != -1) continue;
                comp2[u] = comp2[v];
                dfs2(u);
            }
        };
        int C = 0;
        for(auto v : ts) {
            if (comp2[v] != -1) continue;
            assert(!ban2[v]);
            comp2[v] = C++;
            dfs2(v);
        }
        function<void(int)> dfs3 = [&] (int v) {
            used[v] = 2;
            for(auto u : gr2[v]) {
                if (used[u] == 2) continue;
                dfs3(u);
            }
        };
        if (sz - C <= K) {
            int csz = 0;
            for(auto v : ts) {
                if (used[v] == 2) continue;
                dfs3(v);
                assert(!ban2[v]);
                int f = toc[v][0];
                get_size(f);
                csz++;
            }
            assert(csz <= sz - C);
            break;
        }

        vvi toc2(C);
        for(auto v : ts) {
            for(auto i : toc[v]) {
                toc2[comp2[v]].push_back(i);
                comp[i] = comp2[v];
            }
        }
        swap(toc, toc2);
//        cerr << sz << ' ' << C << '\n';
        sz = C;
//        cerr << '\n';
//        rep(i, n) cerr << ban[i] << ' ' << comp[i] << '\n';
//        cerr << '\n';
    }
//    cerr << ANS << '\n';
    return ans.get();
}
/*
int main() {
    int n, m;
    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;
}*/

Compilation message (stderr)

keys.cpp: In constructor 'EzArray::EzArray(int)':
keys.cpp:22:9: warning: 'EzArray::T' will be initialized after [-Wreorder]
   22 |     int T;
      |         ^
keys.cpp:20:17: warning:   'std::vector<int> EzArray::a' [-Wreorder]
   20 |     vector<int> a;
      |                 ^
keys.cpp:23:5: warning:   when initialized here [-Wreorder]
   23 |     EzArray(int sz = 0) : n(sz), T(1), a() {
      |     ^~~~~~~
keys.cpp: In function 'vi find_reachable(vi, vi, vi, vi)':
keys.cpp:124:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  124 |             if (toc[v].size() > ANS || ban2[v]) {
      |                 ~~~~~~~~~~~~~~^~~~~
keys.cpp:130:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  130 |                 if (toc[v].size() < ANS) {
      |                     ~~~~~~~~~~~~~~^~~~~
keys.cpp:49:10: warning: unused variable 'ok' [-Wunused-variable]
   49 |     bool ok = false;
      |          ^~

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