제출 #583123

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583123		definitelynotmee	늑대인간 (IOI18_werewolf)	C++17	100 / 100	866 ms	143048 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;

struct UnionFind{
    vector<int> pai;
    vector<set<int>> lista;
    UnionFind(int n = 0){
        pai = vector<int>(n);
        lista = vector<set<int>>(n);
        iota(all(pai),0);
        for(int i = 0; i < n; i++)
            lista[i].insert(i);
    }
    int find(int id){
        if(pai[id] == id)
            return id;
        return pai[id] = find(pai[id]);
    }
    void onion(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b)
            return;
        if(lista[a].size() > lista[b].size())
            swap(a,b);
        pai[a] = b;
        for(int i : lista[a])
            lista[b].insert(i);
    }
};

std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int Q = S.size();

    matrix<int> g(n);
    for(int i = 0; i < X.size(); i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    matrix<int>child(n);
    vector<int> pai(n), dirpai(n);
    iota(all(pai),0);
    iota(all(dirpai),0);

    auto find=[&](int id, auto f)->int{
        if(pai[id] == id)
            return id;
        return pai[id] = f(pai[id],f);
    };
    auto onion =[&](int a, int b){
        a = find(a,find), b = find(b,find);
        if(a == b)
            return;
        if(a > b)
            swap(a,b);

        pai[b] = a;
        dirpai[b] = a;
        child[a].push_back(b);
    };

    for(int i = n-1; i >= 0; i--){
        for(int j : g[i]){
            if(j > i)
                onion(i,j);
        }
    }

    // for(int i = 0; i < n; i++){
    //     for(int j : child[i])
    //         cout << "aresta " << i << ' ' << j << '\n';
    // }

    vector<int> tin(n);
    vector<pii> range(n);

    int timer = -1;

    auto dfs =[&](int id, auto dfs)->void{
        tin[id] = ++timer;
        range[id].ff = timer;
        range[id].ss = timer;
        for(int i : child[id]){
            dfs(i,dfs);
            range[id].ss = range[i].ss;
        }
    };

    dfs(0,dfs);

    // for(int i = 0; i < n; i++)
    //     cout << i << " = " << range[i].ff << ' ' << range[i].ss << '\n';

    matrix<int> lift(20,vector<int>(n));
    for(int i = 0; i < n; i++){
        lift[0][i] = dirpai[i];
    }
    for(int i = 1; i < 20; i++){
        for(int j = 0; j < n; j++){
            lift[i][j] = lift[i-1][lift[i-1][j]];
            //cout << "lift " << i << ' ' << j << " = " << lift[i][j] << '\n';
        }
    }

    auto getroot =[&](int id, int l){
        for(int i = 19; i >= 0; i--)
            if(lift[i][id] >= l)
                id = lift[i][id];
        return id;
    };

    matrix<int> queries(n);

    for(int i = 0; i < Q; i++){
        queries[R[i]].push_back(i);
    }

    UnionFind uf(n);

    vector<int> resp(Q);

    for(int i = 0; i < n; i++){
        //cout << i << endl;
        for(int j : g[i]){
            if(j < i)
                uf.onion(tin[i],tin[j]);
        }
        for(int q : queries[i]){
            int root = getroot(S[q],L[q]);
            // cout << "root(" << q << ") = " << root << '\n';
            // cout << "[" << range[root].ff << ',' << range[root].ss << "]\n";
            int rep = uf.find(tin[E[q]]);
            auto it = uf.lista[rep].lower_bound(tin[root]);
            resp[q] = it!=uf.lista[rep].end()&& *it <= range[root].ss;
            // if(resp[q]){
            //     cout << "->" << q << ' ' << *it << '\n';
            // }
        }
    }

    return resp;
}

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

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 0; i < X.size(); i++){
      |                    ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51