oj.uz

Submission #412890

# Submission time Handle Problem Language Result Execution time Memory
412890 2021-05-27T18:33:27 Z mat_v Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 56624 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];
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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14432 KB Output is correct
6 Correct 9 ms 14332 KB Output is correct
7 Correct 8 ms 14396 KB Output is correct
8 Correct 8 ms 14412 KB Output is correct
9 Correct 8 ms 14400 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14432 KB Output is correct
6 Correct 9 ms 14332 KB Output is correct
7 Correct 8 ms 14396 KB Output is correct
8 Correct 8 ms 14412 KB Output is correct
9 Correct 8 ms 14400 KB Output is correct
10 Correct 20 ms 15032 KB Output is correct
11 Correct 17 ms 14924 KB Output is correct
12 Correct 12 ms 14924 KB Output is correct
13 Correct 26 ms 15108 KB Output is correct
14 Correct 26 ms 15104 KB Output is correct
15 Correct 22 ms 15144 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 46604 KB Output is correct
2 Execution timed out 4054 ms 56624 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14432 KB Output is correct
6 Correct 9 ms 14332 KB Output is correct
7 Correct 8 ms 14396 KB Output is correct
8 Correct 8 ms 14412 KB Output is correct
9 Correct 8 ms 14400 KB Output is correct
10 Correct 20 ms 15032 KB Output is correct
11 Correct 17 ms 14924 KB Output is correct
12 Correct 12 ms 14924 KB Output is correct
13 Correct 26 ms 15108 KB Output is correct
14 Correct 26 ms 15104 KB Output is correct
15 Correct 22 ms 15144 KB Output is correct
16 Correct 462 ms 46604 KB Output is correct
17 Execution timed out 4054 ms 56624 KB Time limit exceeded
18 Halted 0 ms 0 KB -