Submission #893233

#	Time	Username	Problem	Language	Result	Execution time	Memory
893233		vjudge1	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	596 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct UF {
    vi e;
    UF(int N) : e(N, -1) {}
    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }
    int join(int u, int v) {
        u = repr(u); v = repr(v);
        if(u == v) return 0;
        if(e[u] > e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        return 1;
    }
    bool same(int u, int v) { return repr(u) == repr(v); }
    void clear() { for(auto &it : e) it = -1; }
};

vi find_roads(int n, vi u, vi v) {
    int m = u.size();
    UF sol(n);
    vector<vi> L(n);
    for(int i = 0; i < m; ++i) {
        L[u[i]].push_back(v[i]);
        L[v[i]].push_back(u[i]);
    }
    vi Re;
    for(int i = 0; i < n; ++i) {
        sol.clear();
        vector<int> Q;
        for(int j = 0; j < m; ++j) {
            if(u[j] != i && v[j] != i) {
                if(sol.join(u[j], v[j])) {
                    Q.push_back(j);
                }
            }
        }
     //   vector<int> Cul;
     //   for(int j = 0; j < m; ++j) {
     //       if(u[j] == i || v[j] == i) {
     //           int x = u[j];
     //           if(x == i) x = v[j];
     //           Cul.push_back(sol.repr(x));
     //       }
     //   }
     //   sort(Cul.begin(), Cul.end());
     //   Cul.resize(unique(Cul.begin(), Cul.end()) - Cul.begin());
     //   auto id = [&](int v) {
     //       return lower_bound(Cul.begin(), Cul.end(), v) - Cul.begin();
     //   };
        map<int, vector<int> > M;
        for(int j = 0; j < m; ++j) {
            if(u[j] == i || v[j] == i) {
                int x = u[j];
                if(x == i) x = v[j];
                M[sol.repr(x)].push_back(j);
            }
        }
        for(auto [cul, vec] : M) {
            vi QQ = Q;
            for(auto [altcul, altvec] : M)
                if(altcul != cul)
                    QQ.push_back(altvec[0]);
            int rem = 0, muchie = 0;
            for(auto it : vec) {
                QQ.push_back(it);
                int v = count_common_roads(QQ);
                QQ.pop_back();
                if(v > rem) {
                    rem = v;
                    muchie = it;
                }
            }
            Re.push_back(muchie);
        }
    }
    sort(Re.begin(), Re.end());
    Re.resize(unique(Re.begin(), Re.end()) - Re.begin());
    return Re;
}

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