답안 #379474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379474	2021-03-18T09:58:46 Z	dantoh000	로카히아 유적 (FXCUP4_lokahia)	C++17	컴파일 오류	0 ms	0 KB

lokahia

#include <bits/stdc++.h>
using namespace std;
#include "lokahia.h"
int Q[205][205];
const int LIM = 400;
vector<int> ord;
int tq = 0;
int query(int i, int j){
    if (i == j) return Q[i][i] = i;
    else if (tq >= LIM) return -1;
    else if (Q[i][j] == -2) {
        tq++;
        return Q[i][j] = Q[j][i] = CollectRelics(i,j);
    }
    else return Q[i][j];
}
int c[205];
int p[205];
int rk[205];
int sz[205];
void init(int n){
    for (int i = 0; i < n; i++){
        p[i] = i;
        rk[i] = 0;
        sz[i] = 1;
    }
}
int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}
void un(int x, int y){
    x = find(x) , y= find(y);
    if (x == y) return;
    if (rk[x] < rk[y]) swap(x,y);
    p[y] = x;
    sz[x] += sz[y];
    if (rk[x] == rk[y]) rk[x]++;
}
vector<ii> v;
int FindBase(int N){
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) Q[i][j] = -2;
    init(N);
    ord.resize(N);
    iota(ord.begin(), ord.end(), 0);
    random_shuffle(ord.begin(),ord.end());
    for (int i = 0; i < N/2; i++){
        int Q = query(ord[2*i],ord[2*i+1]);
        if (Q != -1){
            c[Q]+=2;
            un(Q, ord[2*i]);
            un(Q, ord[2*i+1]);
        }
        else{
            c[ord[2*i]]++;
            c[ord[2*i+1]]++;
        }
    }
    for (int i = 0; i < N; i++){
        if (c[i]) v.push_back({c[i],i});
    }
    sort(v.begin(),v.end());
    int st = v[0].second;
    vector<int> good;
    for (auto x : v){
        if (find(x.second) != find(st)) good.push_back(x.second);
    }
    while (good.size() && tq <= LIM){
        sort(good.begin(),good.end());
        srand(time(NULL));
        random_shuffle(good.begin(),good.end());
        for (auto x : good){
            if (st == x) continue;
            int q = query(st,x);
            if (q != -1){
                if (q > st) st = q;
                un(st,q);
            }
            else bad.push_back(x);
        }
        if (sz[find(st)] > N/2) return st;
        vector<int> bad;
        good.clear();
        for (auto x : bad){
            good.push_back(x);
        }
        bad.clear();
    }
    return -1;
}

Compilation message

lokahia.cpp:39:8: error: 'ii' was not declared in this scope
   39 | vector<ii> v;
      |        ^~
lokahia.cpp:39:10: error: template argument 1 is invalid
   39 | vector<ii> v;
      |          ^
lokahia.cpp:39:10: error: template argument 2 is invalid
lokahia.cpp: In function 'int FindBase(int)':
lokahia.cpp:59:21: error: request for member 'push_back' in 'v', which is of non-class type 'int'
   59 |         if (c[i]) v.push_back({c[i],i});
      |                     ^~~~~~~~~
lokahia.cpp:61:12: error: request for member 'begin' in 'v', which is of non-class type 'int'
   61 |     sort(v.begin(),v.end());
      |            ^~~~~
lokahia.cpp:61:22: error: request for member 'end' in 'v', which is of non-class type 'int'
   61 |     sort(v.begin(),v.end());
      |                      ^~~
lokahia.cpp:62:17: error: invalid types 'int[int]' for array subscript
   62 |     int st = v[0].second;
      |                 ^
lokahia.cpp:64:19: error: 'begin' was not declared in this scope
   64 |     for (auto x : v){
      |                   ^
lokahia.cpp:64:19: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from lokahia.cpp:1:
/usr/include/c++/9/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/9/filesystem:38,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:129,
                 from lokahia.cpp:1:
/usr/include/c++/9/bits/fs_dir.h:516:3: note:   'std::filesystem::__cxx11::begin'
  516 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
lokahia.cpp:64:19: error: 'end' was not declared in this scope
   64 |     for (auto x : v){
      |                   ^
lokahia.cpp:64:19: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from lokahia.cpp:1:
/usr/include/c++/9/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/9/filesystem:38,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:129,
                 from lokahia.cpp:1:
/usr/include/c++/9/bits/fs_dir.h:520:3: note:   'std::filesystem::__cxx11::end'
  520 |   end(recursive_directory_iterator) noexcept
      |   ^~~
lokahia.cpp:78:18: error: 'bad' was not declared in this scope
   78 |             else bad.push_back(x);
      |                  ^~~