제출 #1355380

#제출 시각아이디문제언어결과실행 시간메모리
1355380JooDdae열쇠 (IOI21_keys)C++20
컴파일 에러
0 ms0 KiB
#include "keys.h"
#include <bits/stdc++.h>
using namespace std;

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: In function 'int find(int)':
keys.cpp:6:17: error: 'p' was not declared in this scope
    6 |     return x == p[x] ? x : p[x] = find(p[x]);
      |                 ^
keys.cpp: In function 'int find2(int)':
keys.cpp:10:17: error: 'p2' was not declared in this scope
   10 |     return x == p2[x] ? x : p2[x] = find2(p2[x]);
      |                 ^~
keys.cpp: In function 'bool merge(int, int)':
keys.cpp:18:5: error: 'p' was not declared in this scope
   18 |     p[y] = x, sz[x] += sz[y];
      |     ^
keys.cpp:18:15: error: 'sz' was not declared in this scope
   18 |     p[y] = x, sz[x] += sz[y];
      |               ^~
keys.cpp:20:26: error: 'k' was not declared in this scope; did you mean 'kv'?
   20 |     for(const auto &kv : k[y]) {
      |                          ^
      |                          kv
keys.cpp:22:23: error: 's' was not declared in this scope
   22 |             auto it = s[x].lower_bound({kv, 0});
      |                       ^
keys.cpp:24:17: error: 'nq' was not declared in this scope
   24 |                 nq[x].push_back(it->second), it = s[x].erase(it);
      |                 ^~
keys.cpp:28:27: error: 'nq' was not declared in this scope; did you mean 'nqv'?
   28 |     for(const auto &nqv : nq[y]) nq[x].push_back(nqv);
      |                           ^~
      |                           nqv
keys.cpp:29:33: error: 's' was not declared in this scope
   29 |     for(const auto &[col, to] : s[y]) {
      |                                 ^
keys.cpp:30:12: error: 'k' was not declared in this scope
   30 |         if(k[x].count(col)) {
      |            ^
keys.cpp:31:13: error: 'nq' was not declared in this scope
   31 |             nq[x].push_back(to);
      |             ^~
keys.cpp:36:5: error: 'nxt' was not declared in this scope
   36 |     nxt[x] = -1;
      |     ^~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:43:9: error: 's' was not declared in this scope
   43 |         s[u[i]].insert({c[i], v[i]});
      |         ^
keys.cpp:49:20: error: 'p' was not declared in this scope
   49 |         q.push(i), p[i] = i, p2[i] = i, sz[i] = 1, nxt[i] = -1;
      |                    ^
keys.cpp:49:30: error: 'p2' was not declared in this scope
   49 |         q.push(i), p[i] = i, p2[i] = i, sz[i] = 1, nxt[i] = -1;
      |                              ^~
keys.cpp:49:41: error: 'sz' was not declared in this scope
   49 |         q.push(i), p[i] = i, p2[i] = i, sz[i] = 1, nxt[i] = -1;
      |                                         ^~
keys.cpp:49:52: error: 'nxt' was not declared in this scope
   49 |         q.push(i), p[i] = i, p2[i] = i, sz[i] = 1, nxt[i] = -1;
      |                                                    ^~~
keys.cpp:50:9: error: 'k' was not declared in this scope
   50 |         k[i].insert(r[i]);
      |         ^
keys.cpp:51:19: error: 's' was not declared in this scope
   51 |         auto it = s[i].lower_bound({r[i], 0});
      |                   ^
keys.cpp:53:13: error: 'nq' was not declared in this scope; did you mean 'q'?
   53 |             nq[i].push_back(it->second), it = s[i].erase(it);
      |             ^~
      |             q
keys.cpp:59:12: error: 'nxt' was not declared in this scope
   59 |         if(nxt[u] != -1) continue;
      |            ^~~
keys.cpp:61:16: error: 'nq' was not declared in this scope; did you mean 'q'?
   61 |         while(!nq[u].empty()) {
      |                ^~
      |                q
keys.cpp:66:36: error: 'nxt' was not declared in this scope
   66 |                 for(int i=x;i!=u;i=nxt[i]) merge(i, u);
      |                                    ^~~
keys.cpp:69:17: error: 'nxt' was not declared in this scope
   69 |                 nxt[u] = p2[u] = x;
      |                 ^~~
keys.cpp:69:26: error: 'p2' was not declared in this scope
   69 |                 nxt[u] = p2[u] = x;
      |                          ^~
keys.cpp:76:29: error: 'nxt' was not declared in this scope
   76 |     for(int i=0;i<n;i++) if(nxt[find(i)] == -1) mn = min(mn, sz[p[i]]);
      |                             ^~~
keys.cpp:76:62: error: 'sz' was not declared in this scope
   76 |     for(int i=0;i<n;i++) if(nxt[find(i)] == -1) mn = min(mn, sz[p[i]]);
      |                                                              ^~
keys.cpp:76:65: error: 'p' was not declared in this scope
   76 |     for(int i=0;i<n;i++) if(nxt[find(i)] == -1) mn = min(mn, sz[p[i]]);
      |                                                                 ^
keys.cpp:79:29: error: 'nxt' was not declared in this scope
   79 |     for(int i=0;i<n;i++) if(nxt[p[i]] == -1 && sz[p[i]] == mn) ans[i] = 1;
      |                             ^~~
keys.cpp:79:33: error: 'p' was not declared in this scope
   79 |     for(int i=0;i<n;i++) if(nxt[p[i]] == -1 && sz[p[i]] == mn) ans[i] = 1;
      |                                 ^
keys.cpp:79:48: error: 'sz' was not declared in this scope
   79 |     for(int i=0;i<n;i++) if(nxt[p[i]] == -1 && sz[p[i]] == mn) ans[i] = 1;
      |                                                ^~