Submission #412858

#	Time	Username	Problem	Language	Result	Execution time	Memory
412858		mat_v	Werewolf (IOI18_werewolf)	C++14	0 / 100	175 ms	42116 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){
    a = findpar(a);
    b = findpar(b);
    if(a == b)return;
    if(sajz[a] < sajz[b])swap(a,b);
    dsu[a] = b;
    sajz[b] += sajz[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(c);
                unite(i,c);
            }
        }
    }
    br = 1;
    dfs1(1);

    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(c);
            }
        }
    }
    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]++;
        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;


}

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:65:5: note: in expansion of macro 'ff'
   65 |     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:69:5: note: in expansion of macro 'ff'
   69 |     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:74:5: note: in expansion of macro 'fb'
   74 |     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:86:5: note: in expansion of macro 'ff'
   86 |     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:92:5: note: in expansion of macro 'ff'
   92 |     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:102:5: note: in expansion of macro 'ff'
  102 |     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:107:5: note: in expansion of macro 'ff'
  107 |     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:121:9: note: in expansion of macro 'ff'
  121 |         ff(j,l2,r2){
      |         ^~

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