제출 #1355379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355379		JooDdae	열쇠 (IOI21_keys)	C++20	컴파일 에러	0 ms	0 KiB

keys

#include "keys.h"
using namespace std;

int p[300300], p2[300300], sz[300300], nxt[300300];
vector<int> nq[300300];
set<int> k[300300];
set<pair<int, int>> s[300300];

int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}

int find2(int x) {
    return x == p2[x] ? x : p2[x] = find2(p2[x]);
}

bool merge(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return false;

    // TODO : small to large optimization
    p[y] = x, sz[x] += sz[y];

    for(const auto &kv : k[y]) {
        if(k[x].insert(kv).second) {
            auto it = s[x].lower_bound({kv, 0});
            while(it != s[x].end() && it->first == kv) {
                nq[x].push_back(it->second), it = s[x].erase(it);
            }
        }
    }
    for(const auto &nqv : nq[y]) nq[x].push_back(nqv);
    for(const auto &[col, to] : s[y]) {
        if(k[x].count(col)) {
            nq[x].push_back(to);
        } else {
            s[x].insert({col, to});
        }
    }
    nxt[x] = -1;
    return true;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int n = r.size(), m = v.size();
    for(int i=0;i<m;i++) {
        s[u[i]].insert({c[i], v[i]});
        s[v[i]].insert({c[i], u[i]});
    }

    queue<int> q;
    for(int i=0;i<n;i++) {
        q.push(i), p[i] = i, p2[i] = i, sz[i] = 1, nxt[i] = -1;
        k[i].insert(r[i]);
        auto it = s[i].lower_bound({r[i], 0});
        while(it != s[i].end() && it->first == r[i]) {
            nq[i].push_back(it->second), it = s[i].erase(it);
        }
    }
    
    while(!q.empty()) {
        int u = find(q.front()); q.pop();
        if(nxt[u] != -1) continue;

        while(!nq[u].empty()) {
            int x = find(nq[u].back()); nq[u].pop_back();
            if(u == x) continue;

            if(find2(x) == u) {
                for(int i=x;i!=u;i=nxt[i]) merge(i, u);
                q.push(u);
            } else {
                nxt[u] = p2[u] = x;
            }
            break;
        }
    }

    int mn = 1e9;
    for(int i=0;i<n;i++) if(nxt[find(i)] == -1) mn = min(mn, sz[p[i]]);

    vector<int> ans(n, 0);
    for(int i=0;i<n;i++) if(nxt[p[i]] == -1 && sz[p[i]] == mn) ans[i] = 1;
    return ans;
}

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

keys.cpp:6:1: error: 'set' does not name a type
    6 | set<int> k[300300];
      | ^~~
keys.cpp:7:1: error: 'set' does not name a type
    7 | set<pair<int, int>> s[300300];
      | ^~~
keys.cpp: In function 'bool merge(int, int)':
keys.cpp:24:26: error: 'k' was not declared in this scope; did you mean 'kv'?
   24 |     for(const auto &kv : k[y]) {
      |                          ^
      |                          kv
keys.cpp:26:23: error: 's' was not declared in this scope
   26 |             auto it = s[x].lower_bound({kv, 0});
      |                       ^
keys.cpp:33:33: error: 's' was not declared in this scope
   33 |     for(const auto &[col, to] : s[y]) {
      |                                 ^
keys.cpp:34:12: error: 'k' was not declared in this scope
   34 |         if(k[x].count(col)) {
      |            ^
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:47:9: error: 's' was not declared in this scope
   47 |         s[u[i]].insert({c[i], v[i]});
      |         ^
keys.cpp:51:5: error: 'queue' was not declared in this scope
   51 |     queue<int> q;
      |     ^~~~~
keys.cpp:2:1: note: 'std::queue' is defined in header '<queue>'; did you forget to '#include <queue>'?
    1 | #include "keys.h"
  +++ |+#include <queue>
    2 | using namespace std;
keys.cpp:51:11: error: expected primary-expression before 'int'
   51 |     queue<int> q;
      |           ^~~
keys.cpp:53:9: error: 'q' was not declared in this scope
   53 |         q.push(i), p[i] = i, p2[i] = i, sz[i] = 1, nxt[i] = -1;
      |         ^
keys.cpp:54:9: error: 'k' was not declared in this scope
   54 |         k[i].insert(r[i]);
      |         ^
keys.cpp:55:19: error: 's' was not declared in this scope
   55 |         auto it = s[i].lower_bound({r[i], 0});
      |                   ^
keys.cpp:61:12: error: 'q' was not declared in this scope
   61 |     while(!q.empty()) {
      |            ^