Submission #585062

#	Time	Username	Problem	Language	Result	Execution time	Memory
585062		AugustinasJucas	Werewolf (IOI18_werewolf)	C++14	100 / 100	2894 ms	236136 KiB

werewolf

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

using namespace std;

const int maxN = 2e5 + 10;
const int dd = 18;
int n, m, q;

vector<int> gr[maxN];
vector<int> g1[maxN], g2[maxN];
int tevas2[maxN], mn[maxN];
int tevas1[maxN], mx[maxN];
vector<int> trav1, trav2;
int enter1[maxN], leave1[maxN];
int enter2[maxN], leave2[maxN];
int par1[maxN], par2[maxN];
int lft1[maxN][dd], lft2[maxN][dd];

vector<int> mas;

int fp(int v, int tevas[]) {
    if(tevas[v] == v) return v;
    return tevas[v] = fp(tevas[v],  tevas);
}

void addEdge1(int a, int b) {
    g1[a].push_back(b);
}
void addEdge2(int a, int b) {
    g2[a].push_back(b);
}
void conn1(int a, int b) {
    int pa = fp(a, tevas1);
    int pb = fp(b, tevas1);
    if(pa == pb) return ;
    addEdge1(a, mx[pb]);
    mx[pa] = max(mx[pa], mx[pb]);
    tevas1[pb] = pa;
}

void conn2(int a, int b) {
    int pa = fp(a, tevas2);
    int pb = fp(b, tevas2);
    if(pa == pb) return ;
    addEdge2(a, mn[pb]);
    mn[pa] = min(mn[pa], mn[pb]);
    tevas2[pb] = pa;
}
void print(vector<int> gr[]) {
    for(int i = 0; i < n; i++) {
        cout << i << " jungiasi su ";
        for(auto &x : gr[i]) cout << x << " ";
        cout << endl;
    }
}
void dfs(int v, vector<int> gr[], int enter[], int leave[], vector<int> &trav, int par[]) {
    enter[v] = trav.size();
    trav.push_back(v);
    for(auto x : gr[v]) {
        par[x] = v;
        dfs(x, gr, enter, leave, trav, par);
    }
    leave[v] = trav.size()-1;
}
void calcLft(int tevas[], int lft[][dd]) {
    for(int i = 0; i < n; i++) {
        lft[i][0] = tevas[i];
    }
    for(int i = 1; i < dd; i++) {
        for(int j = 0; j < n; j++) {
            lft[j][i] = lft[lft[j][i-1]][i-1];
        }
    }

}
int findLastLargerThan(int v, int L) { /// su g2
    for(int i = dd-1; i > -1; i--) {
        if(lft2[v][i] >= L) {
            v = lft2[v][i];
        }
    }
    return v;
}
int findLastSmallerThan(int v, int R) {
    for(int i = dd-1; i > -1; i--) {
        if(lft1[v][i] <= R) {
            v = lft1[v][i];
        }
    }
    return v;
}
vector<int> nodes;
vector<int> ret;
void dfs1(int v, vector<int> gr[]) {
    nodes.push_back(v);
    for(auto x : gr[v]) {
        dfs1(x, gr);
    }
}
vector<int> pomed(int v, vector<int> gr[]) {
    nodes.clear();
    dfs1(v, gr);
    return nodes;
}

void calcMas() {
    vector<int> kur(n);
    for(int i = 0; i < n; i++) {
        kur[trav1[i]] = i;
    }
    mas.resize(n);
    for(int i = 0; i < n; i++) {
        mas[i] = kur[trav2[i]];
    }
}
const int dydis = 2e5 + 10;
set<int> medis[dydis * 4];
void idek(int v, int le, int ri, int x, int L = 0, int R = dydis-1) {
    if(le <= L && R <= ri) {
        medis[v].insert(x);
    }else if(L > ri || le > R) {
        return ;
    }else {
        int mid = (L + R) / 2;
        idek(v*2, le, ri, x, L, mid);
        idek(v*2+1, le, ri, x, mid+1, R);
    }
}
void isimk(int v, int le, int ri, int x, int L = 0, int R = dydis-1) {
    if(le <= L && R <= ri) {
        medis[v].erase(x);
    }else if(L > ri || le > R) {
        return ;
    }else {
        int mid = (L + R) / 2;
        isimk(v*2, le, ri, x, L, mid);
        isimk(v*2+1, le, ri, x, mid+1, R);
    }
}
vector<int> reiksIsimt;
void naujink(int v, int le, int ri, int L = 0, int R = dydis-1) {

    if(le <= L && R <= ri) {
        for(auto x : medis[v]) reiksIsimt.push_back(x);
        return ;
    }else if(L > ri || le > R) {
        return ;
    }else {
        for(auto x : medis[v]) reiksIsimt.push_back(x);
        int mid = (L + R) / 2;
        naujink(v*2, le, ri, L, mid);
        naujink(v*2+1, le, ri, mid+1, R);
    }
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                    vector<int> S, vector<int> E,
                                    vector<int> L, vector<int> R) {

    q = L.size();
    n = N;
    m = X.size();
    for(int i = 0; i < m; i++) {
        int a = X[i];
        int b = Y[i];
        gr[a].push_back(b);
        gr[b].push_back(a);
    }
    ret.resize(q);

    for(int i = 0; i < n; i++)  {
        tevas1[i] = tevas2[i] = mn[i] = mx[i] = i;
    }

    for(int i = 0; i < n; i++) {
        int v = i;
        for(auto x : gr[v]) {
            if(x > i) continue;
            conn1(i, x);
        }
    }

    for(int i = n-1; i > -1; i--) {
        int v = i;
        for(auto x : gr[v]) {
            if(x < i) continue;
            conn2(i, x);
        }
    }

    /*cout << "gaunu du grafus:\n";
    print(g1);
    cout << endl;
    print(g2);
*/
    dfs(n-1, g1, enter1, leave1, trav1, par1);
    dfs(0, g2, enter2, leave2, trav2, par2);

    par1[n-1] = n-1;
    par2[0] = 0;

    calcLft(par1, lft1);
    calcLft(par2, lft2);

    calcMas();

    vector<int> lef(q), rig(q);
    vector<int> starts[n], ends[n];

    for(int i = 0; i < q; i++) {

        int rtZmog = findLastLargerThan(S[i], L[i]);
        int rtVilk = findLastSmallerThan(E[i], R[i]);

        /*
        vector<int> zmogus = pomed(rtZmog, g2);
        vector<int> vilkas = pomed(rtVilk, g1);

        cout << i << " querio metu, zmogus: "; for(auto x : zmogus) cout << x << " ";
        cout << endl << "vilkas: "; for(auto x : vilkas) cout << x << " ";
        cout << endl << endl;
        */

        starts[enter2[rtZmog]].push_back(i);
        ends[leave2[rtZmog]].push_back(i);

        lef[i] = enter1[rtVilk];
        rig[i] = leave1[rtVilk];

     //   cout << "queris, ar intervale [" << enter2[rtZmog] << "; " << leave2[rtZmog] << "] yra kazkas is intervalo [" << lef[i] << "; " << rig[i] << "]\n";
    }

    for(auto &x : ret) x = 0;
    //cout << "trav1: "; for(auto x : trav1) cout << x <<  " ";
    //cout << endl << "trav2: "; for(auto x : trav2) cout  << x << " ";
    //cout << endl << "mas: "; for(auto x : mas) cout << x << " ";
    //cout << endl;
    for(int i = 0; i < n; i++) {
        //cout << "i = " << i << endl;
        for(auto x : starts[i]) {
      //      cout << "Idedu " << x << "-aji queri, t.y., ar yra skaicius is intervalo [" << lef[x] << "; " << rig[x] << "] ?" << endl;
            idek(1, lef[x], rig[x], x);
        }
        reiksIsimt.clear();

        naujink(1, mas[i], mas[i]);
    //    cout << "paimu skaiciu " << mas[i] << endl;
        for(auto x : reiksIsimt) {
  //          cout << "ret[" << x << "] = " << 1 << endl;
            ret[x] = 1;
            isimk(1, lef[x], rig[x], x);
        }
        for(auto x : ends[i]) {
//            cout << "ISIMU " << x << "-aji queri, t.y., ar yra skaicius is intervalo [" << lef[x] << "; " << rig[x] << "] ?" << endl;

            isimk(1, lef[x], rig[x], x);
        }
    }
    //cout << "ret: "; for(auto x : ret) cout << x << " "; cout << endl;

    return ret;
}

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