Submission #1188333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188333		anmattroi	Simurgh (IOI17_simurgh)	C++17	0 / 100	77 ms	2628 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>;


int nho[maxn][maxn];

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

    for (int o = 0; o < n; o++) {
        vector<int> indx, suk;
        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]);
            indx.emplace_back(i);
        }
        for (int i = 0; i < n; i++)
        if (o != i) suk.emplace_back(find_set(i));

        sort(suk.begin(), suk.end());
        suk.erase(unique(suk.begin(), suk.end()), suk.end());

        for (int _i = 0; _i < suk.size(); _i++) {
            vector<int> indice = indx;
            for (int i = 0; i < suk.size(); i++)
            if (i != _i)
                for (int j = 0; j < n; j++) if (j != o && find_set(j) == suk[i]) {indice.emplace_back(j); break;}

            vector<int> ADJ;
            for (int i = 0; i < n; i++)
                if (find_set(i) == suk[_i]) if (nho[o][i] != -1) ADJ.emplace_back(nho[o][i]);

            vector<ii> zoe;
            int cnt = -1, cc = -1;
            for (int i : ADJ) {
                if (cl[i] == 1) {
                    cnt = i;
                    continue;
                }
                if (cl[i] == -1) {
                    cc = i;
                    continue;
                }
                indice.emplace_back(i);
                zoe.emplace_back(i, count_common_roads(indice));
                indice.pop_back();
            }
            int mx = 0, dif = 0;
            for (auto [u, v] : zoe) mx = max(mx, v);

            for (auto [u, v] : zoe)
                if (mx != v) {
                    dif = 1;
                    break;
                }

            if (dif) {
                for (auto [u, v] : zoe) {
                    if (v == mx) cl[u] = 1;
                    else cl[u] = -1;
                }
                continue;
            }

            if (cnt == -1 && cc == -1) {
                for (auto [u, v] : zoe) cl[u] = 1;
                continue;
            }

            if (cnt != -1) {
                indice.emplace_back(cnt);
                int T = count_common_roads(indice);
                for (auto [u, v] : zoe) {
                    if (v == T) cl[u] = 1;
                    else cl[u] = -1;
                }
                continue;
            }
            indice.emplace_back(cc);
            int T = count_common_roads(indice);
            for (auto [u, v] : zoe) {
                if (v != T) cl[u] = 1;
                else cl[u] = -1;
            }
        }
    }
    vector<int> ans;
    for (int i = 0; i < m; i++) if (cl[i] == 1) ans.emplace_back(i);
    return ans;
}
/*
5 5
0 1
0 2
0 3
0 4
1 4
0 1 2 3
*/

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