Submission #412902

#	Time	Username	Problem	Language	Result	Execution time	Memory
412902		mat_v	Werewolf (IOI18_werewolf)	C++14	100 / 100	1804 ms	142748 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pb push_back

using namespace std;

int n;
int m;
int q;
vector<int> graf[200005];
vector<int> manji[200005];
int cale[200005][2];
int lca[200005][20][2];
vector<int> veci[200005];
int disc[200005][2];
int out[200005][2];
int dsu[200005];
int sajz[200005];
int findpar(int x){
    if(x == dsu[x])return x;
    return dsu[x] = findpar(dsu[x]);
}
void unite(int a, int b, int idx){
    a = findpar(a);
    b = findpar(b);
    if(a == b)return;
    if(idx == 0){
        if(a < b)dsu[b] = a;
        else dsu[a] = b;
    }
    else{
        if(a < b)dsu[a] = b;
        else dsu[b] = a;
    }
}

int br = 1;
void dfs1(int x){
    disc[x][0] = br;
    lca[x][0][0] = cale[x][0];
    ff(j,1,18){
        lca[x][j][0] = lca[lca[x][j - 1][0]][j - 1][0];
    }
    for(auto c:manji[x]){
        br++;
        dfs1(c);
    }
    out[x][0] = br;
}
void dfs2(int x){
    disc[x][1] = br;
    lca[x][0][1] = cale[x][1];
    ff(j,1,18){
        lca[x][j][1] = lca[lca[x][j - 1][1]][j - 1][1];
    }
    for(auto c:veci[x]){
        br++;
        dfs2(c);
    }
    out[x][1] = br;
}

bool insubtr(int x, int y, int idx){
    ///y u x
    if(disc[y][idx] >= disc[x][idx] && disc[y][idx] <= out[x][idx])return 1;
    return 0;
}

int val[200005];
vector<int> mgs[4 * 200001];

void spoji(int x, int y, int z){
    int l1 = mgs[x].size();
    int l2 = mgs[y].size();
    int br1 = 0, br2 = 0;
    while(br1 < l1 || br2 < l2){
        if(br1 == l1){
            mgs[z].pb(mgs[y][br2]);
            br2++;
            continue;
        }
        if(br2 == l2){
            mgs[z].pb(mgs[x][br1]);
            br1++;
            continue;
        }
        if(mgs[x][br1] < mgs[y][br2]){
            mgs[z].pb(mgs[x][br1]);
            br1++;
        }
        else{
            mgs[z].pb(mgs[y][br2]);
            br2++;
        }
    }
}

void init(int node, int l, int r){
    if(l == r){
        mgs[node].pb(val[l]);
        return;
    }
    int mid = (l + r) / 2;
    init(node * 2, l, mid);
    init(node * 2 + 1, mid + 1, r);
    spoji(node * 2, node * 2 + 1, node);
}

int kolko(int node, int mv, int vv){
    int vel = mgs[node].size();
    int prvi = 0;
    if(mgs[node][vel - 1] < mv)return 0;
    int l = 0, r = vel-1;
    while(l < r){
        int mid = (l + r) / 2;
        if(mgs[node][mid] >= mv)r = mid;
        else l = mid + 1;
    }
    prvi = l;
    if(mgs[node][0] > vv)return 0;
    l = 0, r = vel - 1;
    while(l < r){
        int mid = (l + r + 1) / 2;
        if(mgs[node][mid] <= vv)l = mid;
        else r = mid - 1;
    }
    if(prvi <= l)return 1;
    return 0;
}

int kveri(int node, int l, int r, int levo, int desno, int mv, int vv){
    if(l > r || levo > desno)return 0;
    if(levo > r || l > desno)return 0;
    if(l >= levo && r <= desno){
        return kolko(node, mv, vv);
    }
    int mid = (l + r) / 2;
    return kveri(node * 2, l, mid, levo, desno, mv, vv) + kveri(node * 2 + 1, mid + 1, r, levo, desno, mv, vv);
}

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) {

    n = N;
    m = X.size();
    ff(i,0,m - 1){
        graf[X[i] + 1].pb(Y[i] + 1);
        graf[Y[i] + 1].pb(X[i] + 1);
    }
    ff(i,1,n){
        dsu[i] = i;
        sajz[i] = 1;
        sort(graf[i].begin(), graf[i].end());
    }
    fb(i,n,1){
        for(auto c:graf[i]){
            if(c > i){
                if(findpar(i) == findpar(c))continue;
                int koji = findpar(c);
                manji[i].pb(koji);
                cale[koji][0] = i;
                unite(i,c,0);
            }
        }
    }
    br = 1;
    dfs1(1);

//    ff(i,1,n){
//        cout << manji[i].size() << " ";
//        for(auto c:manji[i])cout << c << " ";
//        cout << "\n";
//    }
//    exit(0);

    ff(i,1,n){
        dsu[i] = i;
        sajz[i] = 1;
        reverse(graf[i].begin(), graf[i].end());
    }

    ff(i,1,n){
        for(auto c:graf[i]){
            if(c < i){
                if(findpar(c) == findpar(i))continue;
                int koji = findpar(c);
                veci[i].pb(koji);
                cale[koji][1] = i;
                unite(i,c,1);
            }
        }
    }
    br = 1;
    dfs2(n);
    ff(i,1,n){
        val[disc[i][1]] = disc[i][0];
    }
    init(1,1,n);
    q = S.size();
    vector<int> ans;
    ff(i,0,q - 1){
        S[i]++;
        E[i]++;
        L[i]++;
        R[i]++;
       // cout << S[i] << " " << E[i] << " " << L[i] << " " << R[i] << "\n";
        int p1 = S[i];
        fb(j,18,0){
            int koji = lca[p1][j][0];
            if(koji > 0 && koji >= L[i])p1 = koji;
        }
        int l1 = disc[p1][0], r1 = out[p1][0];


        int p2 = E[i];
        fb(j,18,0){
            int koji = lca[p2][j][1];
            if(koji > 0 && koji <= R[i])p2 = koji;
        }
        int l2 = disc[p2][1], r2 = out[p2][1];

        int odg = 0;
        if(kveri(1,1,n,l2,r2,l1,r1))odg = 1;

        ans.pb(odg);
    }
    return ans;
}
/*
10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9

*/

Compilation message (stderr)

werewolf.cpp: In function 'void dfs1(int)':
werewolf.cpp:3:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
werewolf.cpp:43:5: note: in expansion of macro 'ff'
   43 |     ff(j,1,18){
      |     ^~
werewolf.cpp: In function 'void dfs2(int)':
werewolf.cpp:3:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
werewolf.cpp:55:5: note: in expansion of macro 'ff'
   55 |     ff(j,1,18){
      |     ^~
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:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
werewolf.cpp:149:5: note: in expansion of macro 'ff'
  149 |     ff(i,0,m - 1){
      |     ^~
werewolf.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
werewolf.cpp:153:5: note: in expansion of macro 'ff'
  153 |     ff(i,1,n){
      |     ^~
werewolf.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
werewolf.cpp:158:5: note: in expansion of macro 'fb'
  158 |     fb(i,n,1){
      |     ^~
werewolf.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
werewolf.cpp:179:5: note: in expansion of macro 'ff'
  179 |     ff(i,1,n){
      |     ^~
werewolf.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
werewolf.cpp:185:5: note: in expansion of macro 'ff'
  185 |     ff(i,1,n){
      |     ^~
werewolf.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
werewolf.cpp:198:5: note: in expansion of macro 'ff'
  198 |     ff(i,1,n){
      |     ^~
werewolf.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
werewolf.cpp:204:5: note: in expansion of macro 'ff'
  204 |     ff(i,0,q - 1){
      |     ^~
werewolf.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
werewolf.cpp:211:9: note: in expansion of macro 'fb'
  211 |         fb(j,18,0){
      |         ^~
werewolf.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
werewolf.cpp:219:9: note: in expansion of macro 'fb'
  219 |         fb(j,18,0){
      |         ^~

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