제출 #558294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558294		Olympia	게임 (IOI14_game)	C++17	0 / 100	1 ms	596 KiB

game

#include <bits/stdc++.h>
#include <game.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("popcnt,avx,avx2")
using namespace std;
struct dsu {
    vector<int> parent;
    vector<int> compSize;
    int n;
    int cc;
    void fill(){
        cc = n;
        parent.resize(n), compSize.resize(n);
        for(int i = 0; i < n; i++){
            parent[i] = i, compSize[i] = 1;
        }
    }
    int find_head(int x){
        int o = x;
        while (x != parent[x]) {
            x = parent[x];
        }
        parent[o] = x;
        return x;
    }
    void join(int x, int y){
        x = find_head(x);
        y = find_head(y);
        if(x == y){
            return;
        }
        cc--;
        if(compSize[x] > compSize[y]){
            swap(x,y);
        }
        parent[x] = y;
        compSize[y] += compSize[x]; 
    }
    bool comp(int x, int y){
        return (find_head(x) == find_head(y));
    }
};
bitset<1500> edges[(int)1500];
set<int> edge[1500];
bitset<1500> e[(int)1500];
dsu d;
void initialize (int n)  {
    d.n = n;
    d.fill();
    vector<pair<int,int> > vec;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            edges[i].set(j, true);
        }
        for (int j = i + 1; j < n; j++) {
            vec.push_back(make_pair(i, j));
        }
    }
    random_shuffle(vec.begin(), vec.end());
    for (auto& p: vec) {
        if (d.comp(p.first, p.second)) {
            continue;
        }
        d.join(p.first, p.second);
        edges[p.first].set(p.second, false);
        edge[p.first].insert(p.second);
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            e[i].set(j);
        }
    }
}
int hasEdge (int u, int v) {
    if (u > v) {
        swap(u, v);
    }
    if (edges[u][v]) {
        e[u].set(v, false);
        return false;
    }
    d.fill();
    for (int i = 0; i < d.n; i++) {
        for (int j: edge[i]) {
            if (make_pair(i, j) != make_pair(u, v)) {
                d.join(i, j);
            }
        }
    }
    if (e[u].size() == 1) {
        return true;
    }
    vector<int> head(d.n);
    int cntr = 0;
    set<int> s;
    vector<int> tot;
    for (int i = 0; i < d.n; i++) {
        head[i] = d.find_head(i);
        s.insert(head[i]);
    }
    tot.push_back(*s.begin()); s.erase(*s.begin()); tot.push_back(*s.begin());
    for (int i = 0; i < d.n; i++) {
        int x = head[i];
        int y;
        if (x == tot[0]) y = tot[1];
        else y = tot[0];
        if (!(e[i] & edges[i]).any()) continue;
        for (int j = i; j < d.n; j++) {
            if (!e[i][j] || !edges[i][j]) continue;
            int y = head[j];
            if (x != y) {
                edges[u].set(v, true);
                edge[u].erase(v);
                e[u].set(v, false);
                edges[i].set(j, false);
                edge[i].insert(j);
                return false;
            }
        }
        assert(false);
    }
    return true;
}

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

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:104:13: warning: variable 'y' set but not used [-Wunused-but-set-variable]
  104 |         int y;
      |             ^
game.cpp:94:9: warning: unused variable 'cntr' [-Wunused-variable]
   94 |     int cntr = 0;
      |         ^~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 27
• Subtask 3: 0 / 58