Submission #412890

#	Time	Username	Problem	Language	Result	Execution time	Memory
412890		mat_v	Werewolf (IOI18_werewolf)	C++14	15 / 100	4054 ms	56624 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];
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;
    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[200005];


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];
    }
    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];
        while(1){
            if(cale[p1][0] > 0 && cale[p1][0] >= L[i])p1 = cale[p1][0];
            else break;
        }
        int l1 = disc[p1][0], r1 = out[p1][0];


        int p2 = E[i];
        while(1){
            if(cale[p2][1] > 0 && cale[p2][1] <= R[i])p2 = cale[p2][1];
            else break;
        }
        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;
}
/*
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 '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:71:5: note: in expansion of macro 'ff'
   71 |     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:75:5: note: in expansion of macro 'ff'
   75 |     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:80:5: note: in expansion of macro 'fb'
   80 |     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:101:5: note: in expansion of macro 'ff'
  101 |     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,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,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:125:5: note: in expansion of macro 'ff'
  125 |     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:147:9: note: in expansion of macro 'ff'
  147 |         ff(j,l2,r2){
      |         ^~

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