Submission #1188203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188203		anmattroi	Simurgh (IOI17_simurgh)	C++17	0 / 100	53 ms	2884 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 i = 0; i < n; i++) {
        if (adj[i].size() != n-1) continue;
        if (count_common_roads(adj[i]) == n-1) return adj[i];
    }
    for (int o = 0; o < n; o++) {
        int nex = (o+1)%n;
        vector<int> indice = adj[nex];
        for (int i = 0; i < indice.size(); i++) {
            if (u[indice[i]] == o || v[indice[i]] == o) {swap(indice.back(), indice[i]); break;}
        }
        indice.pop_back();
        vector<ii> nho;
        for (int i : adj[o]) {
            if (cl[i] == 1) 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;
    }
    vector<int> ans;
    for (int i = 0; i < m; i++) if (cl[i]) ans.emplace_back(i);
//    for (int i : ans) cout << i << ' '; cout << "\n";
    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