oj.uz

Submission #585062

# Submission time Handle Problem Language Result Execution time Memory
585062 2022-06-28T09:37:49 Z AugustinasJucas Werewolf (IOI18_werewolf) C++14
100 / 100
 2894 ms 236136 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 52044 KB Output is correct
2 Correct 23 ms 52052 KB Output is correct
3 Correct 24 ms 51984 KB Output is correct
4 Correct 23 ms 51924 KB Output is correct
5 Correct 29 ms 52008 KB Output is correct
6 Correct 26 ms 51976 KB Output is correct
7 Correct 24 ms 52052 KB Output is correct
8 Correct 26 ms 52048 KB Output is correct
9 Correct 25 ms 51980 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 52044 KB Output is correct
2 Correct 23 ms 52052 KB Output is correct
3 Correct 24 ms 51984 KB Output is correct
4 Correct 23 ms 51924 KB Output is correct
5 Correct 29 ms 52008 KB Output is correct
6 Correct 26 ms 51976 KB Output is correct
7 Correct 24 ms 52052 KB Output is correct
8 Correct 26 ms 52048 KB Output is correct
9 Correct 25 ms 51980 KB Output is correct
10 Correct 32 ms 53316 KB Output is correct
11 Correct 33 ms 53308 KB Output is correct
12 Correct 34 ms 53324 KB Output is correct
13 Correct 32 ms 53448 KB Output is correct
14 Correct 38 ms 53460 KB Output is correct
15 Correct 35 ms 53908 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 132316 KB Output is correct
2 Correct 1113 ms 138268 KB Output is correct
3 Correct 1317 ms 138304 KB Output is correct
4 Correct 1550 ms 158460 KB Output is correct
5 Correct 1456 ms 150040 KB Output is correct
6 Correct 964 ms 140104 KB Output is correct
7 Correct 1247 ms 168068 KB Output is correct
8 Correct 1104 ms 138208 KB Output is correct
9 Correct 1930 ms 175536 KB Output is correct
10 Correct 1576 ms 193772 KB Output is correct
11 Correct 1173 ms 161252 KB Output is correct
12 Correct 2060 ms 174280 KB Output is correct
13 Correct 2882 ms 192264 KB Output is correct
14 Correct 2480 ms 192640 KB Output is correct
15 Correct 2222 ms 192508 KB Output is correct
16 Correct 2325 ms 191608 KB Output is correct
17 Correct 1393 ms 180356 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 52044 KB Output is correct
2 Correct 23 ms 52052 KB Output is correct
3 Correct 24 ms 51984 KB Output is correct
4 Correct 23 ms 51924 KB Output is correct
5 Correct 29 ms 52008 KB Output is correct
6 Correct 26 ms 51976 KB Output is correct
7 Correct 24 ms 52052 KB Output is correct
8 Correct 26 ms 52048 KB Output is correct
9 Correct 25 ms 51980 KB Output is correct
10 Correct 32 ms 53316 KB Output is correct
11 Correct 33 ms 53308 KB Output is correct
12 Correct 34 ms 53324 KB Output is correct
13 Correct 32 ms 53448 KB Output is correct
14 Correct 38 ms 53460 KB Output is correct
15 Correct 35 ms 53908 KB Output is correct
16 Correct 839 ms 132316 KB Output is correct
17 Correct 1113 ms 138268 KB Output is correct
18 Correct 1317 ms 138304 KB Output is correct
19 Correct 1550 ms 158460 KB Output is correct
20 Correct 1456 ms 150040 KB Output is correct
21 Correct 964 ms 140104 KB Output is correct
22 Correct 1247 ms 168068 KB Output is correct
23 Correct 1104 ms 138208 KB Output is correct
24 Correct 1930 ms 175536 KB Output is correct
25 Correct 1576 ms 193772 KB Output is correct
26 Correct 1173 ms 161252 KB Output is correct
27 Correct 2060 ms 174280 KB Output is correct
28 Correct 2882 ms 192264 KB Output is correct
29 Correct 2480 ms 192640 KB Output is correct
30 Correct 2222 ms 192508 KB Output is correct
31 Correct 2325 ms 191608 KB Output is correct
32 Correct 1393 ms 180356 KB Output is correct
33 Correct 1057 ms 141756 KB Output is correct
34 Correct 667 ms 87952 KB Output is correct
35 Correct 1118 ms 141656 KB Output is correct
36 Correct 937 ms 141772 KB Output is correct
37 Correct 1069 ms 141476 KB Output is correct
38 Correct 941 ms 142184 KB Output is correct
39 Correct 1114 ms 148604 KB Output is correct
40 Correct 1725 ms 219552 KB Output is correct
41 Correct 1081 ms 142172 KB Output is correct
42 Correct 822 ms 149404 KB Output is correct
43 Correct 1154 ms 144360 KB Output is correct
44 Correct 1060 ms 140420 KB Output is correct
45 Correct 1647 ms 185152 KB Output is correct
46 Correct 1361 ms 153632 KB Output is correct
47 Correct 2035 ms 192668 KB Output is correct
48 Correct 2072 ms 192512 KB Output is correct
49 Correct 1996 ms 192576 KB Output is correct
50 Correct 2172 ms 192292 KB Output is correct
51 Correct 2801 ms 227248 KB Output is correct
52 Correct 2894 ms 236136 KB Output is correct