제출 #1067272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067272		Ignut	Simurgh (IOI17_simurgh)	C++17	30 / 100	177 ms	2652 KiB

simurgh

// Ignut

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

using namespace std;
using ll = long long;

struct DSU {
    vector<int> p, sz;
    void Init(int n) {
        p.assign(n, 0);
        iota(p.begin(), p.end(), 0);
        sz.assign(n, 1);
    }
    int Get(int v) {
        return p[v] == v ? v : p[v] = Get(p[v]);
    }
    bool Unite(int u, int v) {
        u = Get(u), v = Get(v);
        if (u == v) return false;
        if (sz[u] > sz[v]) swap(u, v);
        sz[v] += sz[u];
        p[u] = v;
        return true;
    }
};

const int N = 555;

vector<int> g[N];

bool ans[N * N];
bool bad[N * N];

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    int m = u.size();
    for (int i = 0; i < m; i ++) {
        g[u[i]].push_back(i);
        g[v[i]].push_back(i);
    }
    DSU dsu;
    dsu.Init(n);
    vector<int> have;
    for (int i = 0; i < m; i ++) {
        if (dsu.Unite(u[i], v[i])) {
            have.push_back(i);
        }
    }

    int cnt = count_common_roads(have);
    while (cnt < n - 1) {
        vector<int> next_have;
        int del_val = -1;
        for (int i : have) {
            if (ans[i]) continue;
            for (int j : have) if (j != i) next_have.push_back(j);
            del_val = i;
            break;
        }
        map<int, int> mp;
        for (int i : next_have) mp[i] ++;
        DSU dsu2; dsu2.Init(n);
        for (int i : next_have) dsu2.Unite(u[i], v[i]);
        bool got = false;
        vector<int> asked;
        for (int i = 0; i < m; i ++) {
            if (mp.count(i)) continue;
            if (bad[i]) continue;
            DSU dsu3 = dsu2;
            if (!dsu3.Unite(u[i], v[i])) continue;

            next_have.push_back(i);
            int c = count_common_roads(next_have);
            if (c > cnt) {
                got = true;
                ans[i] = true;
                have = next_have;
                break;
            }
            else {
                asked.push_back(i);
            }
            next_have.pop_back();
        }
        if (!got) {
            ans[del_val] = true;
        }
        else {
            for (int j : asked) bad[j] = true;
        }
        cnt = count_common_roads(have);
    }
    return have;   
}

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