Submission #1067294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067294		Ignut	Simurgh (IOI17_simurgh)	C++17	51 / 100	110 ms	2780 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]);
        vector<int> c_sm, c_eq, c_bg;
        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) {
                c_bg.push_back(i);
            }
            else if (c == cnt) {
                c_eq.push_back(i);
            }
            else {
                c_sm.push_back(i);
            }
            next_have.pop_back();
        }

        next_have.clear();
        if (!c_bg.empty()) {
            for (int j : c_eq) bad[j] = true;
            for (int j : c_bg) {
                ans[j] = true;
            }
        }
        else {
            for (int j : c_sm) bad[j] = true;
            for (int j : c_eq) {
                ans[j] = true;
            }
        }
        dsu2.Init(n);
        for (int j = 0; j < m; j ++) {
            if (ans[j]) {
                next_have.push_back(j);
                dsu2.Unite(u[j], v[j]);
            }
        }
        for (int j = 0; j < m; j ++) {
            if (next_have.size() == n - 1) break;
            if (ans[j]) continue;
            if (bad[j]) continue;
            DSU dsu3 = dsu2;
            if (!dsu3.Unite(u[j], v[j])) continue;
            next_have.push_back(j);
            dsu2.Unite(u[j], v[j]);
        }
        have = next_have;
        
        cnt = count_common_roads(have);
    }
    return have;   
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:107:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |             if (next_have.size() == n - 1) break;
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~
simurgh.cpp:54:13: warning: variable 'del_val' set but not used [-Wunused-but-set-variable]
   54 |         int del_val = -1;
      |             ^~~~~~~

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