제출 #893253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
893253		vjudge1	Simurgh (IOI17_simurgh)	C++17	30 / 100	226 ms	2964 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; }
};

int ccr(vi V) {
    sort(V.begin(), V.end());
    int hsh = 0;
    for(auto it : V)
        hsh = (1ll *hsh * 215 + it) % 1000000009;
    static map<int, int> M;
    if(M.count(hsh)) return M[hsh];
    int v = count_common_roads(V);
    M[hsh] = v;
    return v;
}

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, idk = 0;
            vector<pair<int, int> > U;
            for(auto it : vec) {
                QQ.push_back(it);
                int v = ccr(QQ);
                QQ.pop_back();
                U.push_back({it, v});
                if(v > rem) {
                    rem = v;
                }
            }
            for(auto [it, v] : U) {
                if(v == rem) {
                    Re.push_back(it);
                }
            }
        }
    }
    sort(Re.begin(), Re.end());
    Re.resize(unique(Re.begin(), Re.end()) - Re.begin());
    assert(Re.size() == (n - 1));
    return Re;
} 

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:84:26: warning: unused variable 'muchie' [-Wunused-variable]
   84 |             int rem = 0, muchie = 0, idk = 0;
      |                          ^~~~~~
simurgh.cpp:84:38: warning: unused variable 'idk' [-Wunused-variable]
   84 |             int rem = 0, muchie = 0, idk = 0;
      |                                      ^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp:104:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |     assert(Re.size() == (n - 1));
      |            ~~~~~~~~~~^~~~~~~~~~

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