Submission #443143

#	Time	Username	Problem	Language	Result	Execution time	Memory
443143		JovanB	Werewolf (IOI18_werewolf)	C++17	100 / 100	1184 ms	149312 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAXN = 200000;

struct Edge{
    int a, b, c;
    bool operator <(const Edge &x){
        return c < x.c;
    }
};

struct DSU{
    int n;
    int par[MAXN+5];
    int label[MAXN+5];
    int sz[MAXN+5];
    DSU(int g){
        n = g;
        for(int i=1; i<=n; i++){
            par[i] = i;
            label[i] = i;
            sz[i] = 1;
        }
    }
    int root(int x){ return (par[x] == x ? x : par[x] = root(par[x])); }
    void povezi(int a, int b, int lab){
        if(sz[a] < sz[b]) swap(a, b);
        label[a] = lab;
        sz[a] += sz[b];
        par[b] = a;
    }
};

const int LOG = 20;

struct PMST{
    int n;
    vector <pair <int, int>> graf[2*MAXN+5];
    int L[2*MAXN+5];
    int R[2*MAXN+5];
    int val[2*MAXN+5];
    int par[2*MAXN+5][LOG+1];
    int niz[MAXN+5];
    int tn = 0;
    void dfs(int v, int p, int w){
        val[p] = w;
        par[v][0] = p;
        for(int j=1; j<=LOG; j++) par[v][j] = par[par[v][j-1]][j-1];
        L[v] = 2*MAXN+5;
        R[v] = 0;
        for(auto c : graf[v]){
            dfs(c.first, v, c.second);
            L[v] = min(L[v], L[c.first]);
            R[v] = max(R[v], R[c.first]);
        }
        if(!graf[v].size()){
            tn++;
            L[v] = R[v] = tn;
            niz[tn] = v;
        }
    }
};

PMST tree1, tree2;

int l1[MAXN+5];
int r1[MAXN+5];
int l2[MAXN+5];
int r2[MAXN+5];
int gde[MAXN+5];

int dizi_max(int v, int lm){
    for(int j=LOG; j>=0; j--) if(tree1.val[tree1.par[v][j]] <= lm) v = tree1.par[v][j];
    return v;
}

int dizi_min(int v, int lm){
    for(int j=LOG; j>=0; j--) if(tree2.val[tree2.par[v][j]] >= lm) v = tree2.par[v][j];
    return v;
}

vector <int> queries[MAXN+5];

int bit[MAXN+5];

void addbit(int x){
    while(x <= MAXN){
        bit[x]++;
        x += x & -x;
    }
}

int getbit(int x){
    int res = 0;
    while(x){
        res += bit[x];
        x -= x & -x;
    }
    return res;
}

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 m = X.size();
    vector <Edge> e1, e2;
    for(int i=0; i<m; i++){
        int a = X[i] + 1;
        int b = Y[i] + 1;
        e1.push_back({a, b, max(a, b)});
        e2.push_back({a, b, min(a, b)});
    }
    sort(e1.begin(), e1.end());
    sort(e2.begin(), e2.end());
    reverse(e2.begin(), e2.end());
    int n = N;
    DSU dsu1(n);
    DSU dsu2(n);
    int lab1 = n;
    int lab2 = n;
    for(auto edge : e1){
        int a = edge.a;
        int b = edge.b;
        int c = edge.c;
        int a1 = dsu1.root(a);
        int b1 = dsu1.root(b);
        if(a1 == b1) continue;
        lab1++;
        tree1.graf[lab1].push_back({dsu1.label[a1], c});
        tree1.graf[lab1].push_back({dsu1.label[b1], c});
        dsu1.povezi(a1, b1, lab1);
    }
    tree1.n = lab1;
    for(auto edge : e2){
        int a = edge.a;
        int b = edge.b;
        int c = edge.c;
        int a1 = dsu2.root(a);
        int b1 = dsu2.root(b);
        if(a1 == b1) continue;
        lab2++;
        tree2.graf[lab2].push_back({dsu2.label[a1], c});
        tree2.graf[lab2].push_back({dsu2.label[b1], c});
        dsu2.povezi(a1, b1, lab2);
    }
    tree2.n = lab2;
    tree1.dfs(lab1, 0, 10*MAXN);
    cout << endl;
    tree2.dfs(lab2, 0, 0);
    vector <int> soln;
    int qrs = S.size();
    for(int i=0; i<qrs; i++) soln.push_back(0);
    for(int i=0; i<qrs; i++){
        swap(S[i], E[i]);
        S[i]++;
        E[i]++;
        L[i]++;
        R[i]++;
        int v = dizi_max(S[i], R[i]);
        l1[i] = tree1.L[v];
        r1[i] = tree1.R[v];
        v = dizi_min(E[i], L[i]);
        l2[i] = tree2.L[v];
        r2[i] = tree2.R[v];
        queries[l2[i]-1].push_back(-(i+1));
        queries[r2[i]].push_back(i+1);
    }
    for(int i=1; i<=n; i++){
        gde[tree1.niz[i]] = i;
    }
    for(int i=1; i<=n; i++){
        tree1.niz[i] = gde[tree1.niz[i]];
        tree2.niz[i] = gde[tree2.niz[i]];
    }
    for(int i=1; i<=n; i++){
        addbit(tree2.niz[i]);
        for(auto ind : queries[i]){
            int kf = 1;
            if(ind < 0){
                kf = -1;
                ind = -ind;
            }
            soln[ind-1] += kf*getbit(r1[ind-1]);
            soln[ind-1] -= kf*getbit(l1[ind-1] - 1);
        }
    }
    for(int i=0; i<qrs; i++) if(soln[i] > 0) soln[i] = 1;
    return soln;
}

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