Submission #1188208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188208		anmattroi	Simurgh (IOI17_simurgh)	C++17	0 / 100	77 ms	2888 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define maxn 505
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

vector<int> adj[maxn];

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    int m = u.size();
    vector<int> cl(m+1, 0);
    for (int i = 0; i < m; i++) {
        adj[u[i]].emplace_back(i);
        adj[v[i]].emplace_back(i);
    }

    for (int o = 0; o < n; o++) {
        vector<int> indice;
        if (1) {
            vector<int> par(n);
            iota(par.begin(), par.end(), 0);
            function<int(int)> find_set = [&](int v) {
                return par[v] == v ? v : par[v] = find_set(par[v]);
            };
            for (int i = 0; i < m; i++)
            if (u[i] != o && v[i] != o && find_set(u[i]) != find_set(v[i])) {
                par[find_set(u[i])] = find_set(v[i]);
                indice.emplace_back(i);
            }
        }
        vector<ii> nho;
        int cnt = -1;
        for (int i : adj[o]) {
            if (cl[i] == 1) {
                cnt = i;
                continue;
            }

            indice.emplace_back(i);
            nho.emplace_back(i, count_common_roads(indice));
            indice.pop_back();
        }
//        for (auto [u, v] : nho) cout << u << ' ' << v << "\n";
//        cout << "----------------\n";
        int mx = 0, dif = 0;
        for (auto [u, v] : nho) mx = max(mx, v);
        for (auto [u, v] : nho)
        if (mx != v) {dif = 1; break;}
        if (dif) {
            for (auto [u, v] : nho) if (v == mx) cl[u] = 1;
            continue;
        }
        if (cnt == -1) {
            for (auto [u, v] : nho) cl[u] = 1;
            continue;
        }
        indice.emplace_back(cnt);
        int T = count_common_roads(indice);
        assert(mx != T);
        for (auto [u, v] : nho) if (v == T) cl[u] = 1;
    }
    vector<int> ans;
    for (int i = 0; i < m; i++) if (cl[i]) ans.emplace_back(i);
    return ans;
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/

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