Submission #798349

#	Time	Username	Problem	Language	Result	Execution time	Memory
798349		PixelCat	Simurgh (IOI17_simurgh)	C++14	30 / 100	206 ms	4220 KiB

simurgh

#include "simurgh.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 500;

vector<pii> adj[MAXN + 10];  // { node, edge id }

struct Tree {
    set<int> edge;
    set<int> susid;
    int par[MAXN + 10];
    int dep[MAXN + 10];
    int peid[MAXN + 10];
    vector<int> get_edges() {
        vector<int> ids;
        for(auto &i:edge) ids.eb(i);
        return ids;
    }
    int query() {
        // cerr << "query:";
        // out();
        return count_common_roads(get_edges());
    }
    void dfs(int x, int p, int d, int pe, bool tree_edge_only = true) {
        par[x] = p;
        dep[x] = d;
        peid[x] = pe;
        for(auto &i:adj[x]) if(i.F != p && dep[i.F] == 0) {
            if(tree_edge_only && !edge.count(i.S)) continue;
            else if(!tree_edge_only) {
                edge.insert(i.S); susid.insert(i.S);
            }
            dfs(i.F, x, d + 1, i.S, tree_edge_only);
        }
    }
    void add_edge(int a, int b, int id) {
        if(edge.count(id)) return;
        memset(dep, 0, sizeof(dep));
        dfs(0, -1, 1, -1);
        int cnt = query();
        while(a != b) {
            if(dep[a] < dep[b]) swap(a, b);
            int id2 = peid[a];
            if(susid.count(id2)) {
                edge.erase(id2);
                edge.insert(id);
                if(query() > cnt) {
                    susid.erase(id);
                    return;
                }
                edge.erase(id);
                edge.insert(id2);
            }
            a = par[a];
        }
    }
    void out() {
        for(auto &i:get_edges()) {
            cerr << i << " ";
        }
        cerr << "\n";
    }
} tr;

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
    int M = sz(U);
    For(i, 0, M - 1) {
        adj[U[i]].eb(V[i], i);
        adj[V[i]].eb(U[i], i);
    }
    mt19937_64 rng(time(NULL));
    For(i, 0, N - 1) shuffle(all(adj[i]), rng);
    tr.dfs(0, -1, 1, -1, false);
    vector<int> eid(M);
    For(i, 0, M - 1) eid[i] = i;
    shuffle(all(eid), rng);
    for(auto &i:eid) {
        tr.add_edge(U[i], V[i], i);
    }
    return tr.get_edges();

    // vector<int> r(n - 1);
    // for(int i = 0; i < n - 1; i++)
    //     r[i] = i;
    // int common = count_common_roads(r);
    // if(common == n - 1)
    //     return r;
    // r[0] = n - 1;
    // return r;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30