Submission #1188480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188480		anmattroi	Simurgh (IOI17_simurgh)	C++17	19 / 100	81 ms	3708 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], cnt[maxn], cool[maxn], nexCool[maxn];

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

    for (int i = 0; i < n; i++) {
        vector<int> indice;
        for (int j = 0; j < n; j++) if (i != j) indice.emplace_back(nho[i][j]);
        cnt[i] = count_common_roads(indice);
        if (cnt[i] == n-1) return indice;
    }

    for (int i = 0; i < n-1; i++) {
        int mn = INT_MAX;
        vector<int> indice;
        if (i == 0) {
            for (int j = 1; j < n-1; j++) indice.emplace_back(nho[j][j+1]);
        } else if (i == n-1) {
            for (int j = 0; j < n-2; j++) indice.emplace_back(nho[j][j+1]);
        } else {
            for (int j = 0; j < i-1; j++) indice.emplace_back(nho[j][j+1]);
            indice.emplace_back(nho[i-1][i+1]);
            for (int j = i+1; j < n-1; j++) indice.emplace_back(nho[j][j+1]);
        }
        int dem = 0;
        for (int o = 0; o < n; o++)
        if (o != i) {
            indice.emplace_back(nho[o][i]);
            mn = min(mn, count_common_roads(indice));
            indice.pop_back();
            if (++dem > cnt[i]) break;
        }
        indice.emplace_back(nho[i][i+1]);
        cool[i] = (count_common_roads(indice) != mn);
        indice.pop_back();
        if (i < n-2) {
            indice.emplace_back(nho[i][i+2]);
            nexCool[i] = (count_common_roads(indice) != mn);
        }
        if (cool[i]) cl[nho[i][i+1]] = 1;
    }

    for (int o = 0; o < n; o++) {
        vector<int> lis;
        for (int i = 0; i < n; i++) if (o != i) lis.emplace_back(i);
        for (int p = 1; p <= cnt[o]; p++) {
            function<int(int)> ok = [&](int x) {
                vector<int> indice;
                for (int i = 0; i <= x; i++)
                    indice.emplace_back(nho[o][lis[i]]);

                for (int i = x; i < n-2; i++)
                    indice.emplace_back(nho[lis[i]][lis[i+1]]);

                int ans = count_common_roads(indice);
                for (int i = x; i < n-2; i++) {
                    if (lis[i] + 1 == lis[i+1]) ans -= cool[lis[i]];
                    else ans -= nexCool[lis[i]];
                }
                return ans;
            };

            int lo = -1, hi = n-2;
            while (hi-lo > 1) {
                int mid = (lo + hi) >> 1;
                if (ok(mid) >= p) hi = mid;
                else lo = mid;
            }

            cl[nho[o][lis[hi]]] = 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: 19 / 19
• Subtask 5: 0 / 30