oj.uz

Submission #412878

# Submission time Handle Problem Language Result Execution time Memory
412878 2021-05-27T18:11:32 Z mat_v Werewolf (IOI18_werewolf) C++14
0 / 100
 404 ms 45048 KB 
#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];
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;
                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;
}
/*
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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 404 ms 45048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14412 KB Output isn't correct
2 Halted 0 ms 0 KB -