Submission #412871

#	Time	Username	Problem	Language	Result	Execution time	Memory
412871		mat_v	Werewolf (IOI18_werewolf)	C++14	0 / 100	176 ms	33672 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[100005];
vector<int> manji[100005];
vector<int> veci[100005];
int disc[100005][2];
int out[100005][2];
int dsu[100005];
int sajz[100005];
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;
    for(auto c:manji[x]){
        br++;
        dfs1(c);
    }
    out[x][0] = br;
}
void dfs2(int x){
    disc[x][1] = br;
    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[100005];


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;
                manji[i].pb(findpar(c));
                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;
                veci[i].pb(findpar(c));
                unite(i,c,1);
            }
        }
    }
    br = 1;
    dfs2(n);
    ff(i,1,n){
        val[disc[i][1]] = disc[i][0];
    }
    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];
        if(insubtr(L[i], S[i], 0))p1 = L[i];
        int l1 = disc[p1][0], r1 = out[p1][0];


        int p2 = E[i];
        if(insubtr(R[i], E[i], 1))p2 = R[i];
        int l2 = disc[p2][1], r2 = out[p2][1];

        int odg = 0;
        ff(j,l2,r2){
            if(val[j] >= l1 && val[j] <= r1)odg = 1;
        }
        ans.pb(odg);
    }
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Compilation message (stderr)

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:70:5: note: in expansion of macro 'ff'
   70 |     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:74:5: note: in expansion of macro 'ff'
   74 |     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:79:5: note: in expansion of macro 'fb'
   79 |     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:98:5: note: in expansion of macro 'ff'
   98 |     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:104:5: note: in expansion of macro 'ff'
  104 |     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:115:5: note: in expansion of macro 'ff'
  115 |     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:120:5: note: in expansion of macro 'ff'
  120 |     ff(i,0,q - 1){
      |     ^~
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:136:9: note: in expansion of macro 'ff'
  136 |         ff(j,l2,r2){
      |         ^~

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