Submission #542921

#	Time	Username	Problem	Language	Result	Execution time	Memory
542921		zggf	Werewolf (IOI18_werewolf)	C++14	0 / 100	1279 ms	524288 KiB

werewolf

#include "werewolf.h"
#define f first
#define s second
#include <bits/stdc++.h>

using namespace std;

bool odw[200100];
bool odw2[200100];
vector<int> graf[200100];
vector<int> maksi[200100], cent[200100], nr[200100], wart[200100];
vector<int> p1, sz1, par[20], szi[20];
vector<unordered_map<int, int>> rep[20];

int find(int x, vector<int> &parent){
    if(parent[x]==-1) return x;
    parent[x] = find(parent[x], parent);
    return parent[x];
}

void join(int a, int b, vector<int> &parent, vector<int> &ranga, int pt=-1){
    a = find(a, parent);
    b = find(b, parent);
    //cout<<"join: "<<a<<" "<<b<<'\n';
    if(a==b) return;
    if(ranga[a]>ranga[b]){
        parent[b] =a;
        if(pt!=-1){
            maksi[a][pt] = max(maksi[a][pt], maksi[b][pt]);
            for(auto it:rep[pt][b]){
                if(it.s!=0) rep[pt][a][it.f] = it.s;
            }
            rep[pt][b].clear();
        }
    }else if(ranga[b]>ranga[a]){
        parent[a] = b;
        if(pt!=-1){
            maksi[b][pt] = max(maksi[a][pt], maksi[b][pt]);
            for(auto it:rep[pt][a]){
                if(it.s!=0) rep[pt][b][it.f] = it.s;
            }
            rep[pt][a].clear();
        }
    }else{
        parent[b] = a;
        if(pt!=-1){
            maksi[a][pt] = max(maksi[a][pt], maksi[b][pt]);
            for(auto it:rep[pt][b]){
                if(it.s!=0) rep[pt][a][it.f] = it.s;
            }
            rep[pt][b].clear();
        }
        ranga[a]++;
    }
}

vector<int> G[200100];
vector<int> bylo;
vector<int> sz;

void dfs(int x, int pr=-1){
    sz[x] = 1;
    for(int it:G[x]){
        if(it!=pr){
            dfs(it, x);
            sz[x]+=sz[it];
        } 
    }
}

int centroid(int x){
    for(int it:G[x]){
        if(bylo[it])continue;
        if(sz[x]-sz[it]<sz[it]){
            swap(sz[x], sz[it]);
            sz[x] = sz[it]-sz[x];
            return centroid(it);
        }
    }

    return x;
}

int globNr, globCent;
void dfs2(int x, int pr, int mini){
    mini = min(mini, x);
    nr[x].push_back(globNr);
    cent[x].push_back(globCent);
    wart[x].push_back(mini);
    maksi[x].push_back(mini);
    //cout<<"cent: "<<globCent<<" x: "<<x<<" wart: "<<mini<<'\n';
    int pt = wart[x].size()-1;
    rep[pt][x][globNr] = x+1;
    for(auto it:G[x]){
        if(it!=pr&&!bylo[it]){
            dfs2(it, x, mini);
        }
    }
}

void solve(int x){
    x = centroid(x);    
    bylo[x] = true;

    globCent = x;
    globNr = 0;

    nr[x].push_back(-1);
    cent[x].push_back(globCent);
    wart[x].push_back(x);
    maksi[x].push_back(x);
    for(auto it:G[x]){
        if(!bylo[it]){
            dfs2(it, x, x);
            globNr++;
        }
    }
    for(auto it:G[x]){
        if(!bylo[it]) solve(it);
    }
}

void makeTree(int N){
    p1.resize(N, -1);
    sz.resize(N);
    sz1.resize(N);
    bylo.resize(N);
    for(int i = 0; i < 20; i++){
        szi[i].resize(N);
        par[i].resize(N, -1);
        rep[i].resize(N);
    }
    for(int i = N-1; i>=0; i--){
        odw2[i] = true;
        for(auto it:graf[i]){
            if(odw2[it]){
                if(find(it, p1)!=find(i, p1)){
                    join(it, i, p1, sz1);
                    G[it].push_back(i);
                    G[i].push_back(it); 
                }
            }
        }
    }
    dfs(0);
    solve(0);
}

void add(int x){
    odw[x] = true;
    for(auto it:graf[x]){
        if(odw[it]){
            //cout<<"ADD: "<<x<<" "<<it<<'\n';
            int pt = 0;
            while(pt<cent[it].size()&&pt<cent[x].size()&&cent[it][pt]==cent[x][pt]){
                join(it, x, par[pt], szi[pt], pt);
                pt++;
            }
        }
    }
}

bool qur(int a, int b, int k){
    int pt = 0;
    if(!odw[b]) return false;
    while(pt<cent[a].size()){
        int w1 = wart[a][pt];
        int vb = find(b, par[pt]);
        int w2 = maksi[vb][pt];
        //cout<<"A: "<<a<<" B: "<<b<<" K: "<<k<<" w1: "<<w1<<" w2: "<<w2<<'\n';
        if(min(w1, w2)>=k) return true;
        b = rep[pt][vb][nr[a][pt]];
        b--;
        //cout<<b<<'\n';
        pt++;
        if(b<0) return false;
    }
    return false;
}

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();
    int M = X.size();
    for(int i = 0; i < M; i++){
        graf[X[i]].push_back(Y[i]); 
        graf[Y[i]].push_back(X[i]); 
    }
    makeTree(N);
    vector<pair<pair<pair<int, int>, pair<int, int>>, int>> inp;
    for(int i = 0; i < Q; i++){
        inp.push_back({{{R[i], L[i]}, {S[i], E[i]}}, i});
    }
    sort(inp.begin(), inp.end());
    int poprz = 0;
    vector<int> A(Q);
    for(int i = 0; i < inp.size(); i++){
        int l = inp[i].f.f.s;
        int r = inp[i].f.f.f;
        int a = inp[i].f.s.f;
        int b = inp[i].f.s.s;
        while(poprz<=r){
            add(poprz);
            poprz++; 
        }
        //cout<<qur(a, b, l)<<'\n';
        A[inp[i].s]  = qur(a, b, l);
    }
    return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'void add(int)':
werewolf.cpp:155:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |             while(pt<cent[it].size()&&pt<cent[x].size()&&cent[it][pt]==cent[x][pt]){
      |                   ~~^~~~~~~~~~~~~~~~
werewolf.cpp:155:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |             while(pt<cent[it].size()&&pt<cent[x].size()&&cent[it][pt]==cent[x][pt]){
      |                                       ~~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'bool qur(int, int, int)':
werewolf.cpp:166:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     while(pt<cent[a].size()){
      |           ~~^~~~~~~~~~~~~~~
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:198:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<std::pair<int, int>, std::pair<int, int> >, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |     for(int i = 0; i < inp.size(); i++){
      |                    ~~^~~~~~~~~~~~

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