Submission #292115

#	Time	Username	Problem	Language	Result	Execution time	Memory
292115		Fasho	Werewolf (IOI18_werewolf)	C++14	34 / 100	638 ms	61036 KiB

werewolf

#include <bits/stdc++.h>
 
using namespace std;
using vi=vector<int>;
#define rep(n) for (int i=0; i<n; i++)
const int c=200002;
int m, q, hely[c], mini[c][20], maxi[c][20], cnt;
vi sz[c], sol;
bool kis[c], nagy[c], v[c], jo;
void kdfs(int a, int b) {
    kis[a]=1;
    rep(sz[a].size()) {
        int x=sz[a][i];
        if (!kis[x] && x<=b) kdfs(x, b);
    }
}
void ndfs(int a, int b) {
    nagy[a]=1;
    rep(sz[a].size()) {
        int x=sz[a][i];
        if (!nagy[x] && x>=b) ndfs(x, b);
    }
}
void dfs(int a) {
    v[a]=true, mini[cnt][0]=a, maxi[cnt][0]=a, hely[a]=cnt, cnt++;
    rep(sz[a].size()) {
        int x=sz[a][i];
        if (!v[x]) dfs(x);
    }
}
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
    m=x.size(), q=s.size();
    rep(m) sz[x[i]].push_back(y[i]), sz[y[i]].push_back(x[i]);
/*
    if (n<=3000 && q<=3000) {
        rep(q) {
            jo=0;
            rep(n) kis[i]=0, nagy[i]=0;
            kdfs(e[i], r[i]);
            ndfs(s[i], l[i]);
            rep(n) if (kis[i] && nagy[i]) jo=1;
            sol.push_back(jo);
        }
        return sol;
    }
*/
    rep(n) if (!v[i] && sz[i].size()==1) dfs(i);
    for (int j=1; j<20; j++) rep(n) {
        int p=min(n-1, i+(1<<(j-1)));
        mini[i][j]=min(mini[i][j-1], mini[p][j-1]);
        maxi[i][j]=max(maxi[i][j-1], maxi[p][j-1]);
    }
    rep(q) {
        int em=hely[s[i]], fa=hely[e[i]];
        if (em<fa) {
            for (int j=19; j>=0; j--) if (em<n && mini[em][j]>=l[i]) em+=(1<<j);
            for (int j=19; j>=0; j--) {
                int x=max(0, fa-(1<<j)+1);
                if (maxi[x][j]<=r[i]) fa=x-1;
            }
            sol.push_back((em>=n || fa==-1 || em-fa>1));
        } else {
            for (int j=19; j>=0; j--) if (fa<n && maxi[fa][j]<=r[i]) fa+=(1<<j);
            for (int j=19; j>=0; j--) {
                int x=max(0, em-(1<<j)+1);
                if (mini[x][j]>=l[i]) em=x-1;
            }
            sol.push_back((fa>=n || em==-1 || fa-em>1));
        }
    }
    return sol;
}

Compilation message (stderr)

werewolf.cpp: In function 'void kdfs(int, int)':
werewolf.cpp:5:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(n) for (int i=0; i<n; i++)
      |                              ~^~~~~~~~
    6 | const int c=200002;
      | ~~~~~~~~~~~~~~~~~~~            
    7 | int m, q, hely[c], mini[c][20], maxi[c][20], cnt;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    8 | vi sz[c], sol;
      | ~~~~~~~~~~~~~~                 
    9 | bool kis[c], nagy[c], v[c], jo;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   10 | void kdfs(int a, int b) {
      | ~~~~~~~~~~~~~~~~~~~~~~~~~      
   11 |     kis[a]=1;
      |     ~~~~~~~~~                  
   12 |     rep(sz[a].size()) {
      |     ~~~~~~~~~~~~~~~~           
werewolf.cpp:12:5: note: in expansion of macro 'rep'
   12 |     rep(sz[a].size()) {
      |     ^~~
werewolf.cpp: In function 'void ndfs(int, int)':
werewolf.cpp:5:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(n) for (int i=0; i<n; i++)
      |                              ~^~~~~~~~
    6 | const int c=200002;
      | ~~~~~~~~~~~~~~~~~~~            
    7 | int m, q, hely[c], mini[c][20], maxi[c][20], cnt;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    8 | vi sz[c], sol;
      | ~~~~~~~~~~~~~~                 
    9 | bool kis[c], nagy[c], v[c], jo;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   10 | void kdfs(int a, int b) {
      | ~~~~~~~~~~~~~~~~~~~~~~~~~      
   11 |     kis[a]=1;
      |     ~~~~~~~~~                  
   12 |     rep(sz[a].size()) {
      |     ~~~~~~~~~~~~~~~~~~~        
   13 |         int x=sz[a][i];
      |         ~~~~~~~~~~~~~~~        
   14 |         if (!kis[x] && x<=b) kdfs(x, b);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   15 |     }
      |     ~                          
   16 | }
      | ~                              
   17 | void ndfs(int a, int b) {
      | ~~~~~~~~~~~~~~~~~~~~~~~~~      
   18 |     nagy[a]=1;
      |     ~~~~~~~~~~                 
   19 |     rep(sz[a].size()) {
      |     ~~~~~~~~~~~~~~~~           
werewolf.cpp:19:5: note: in expansion of macro 'rep'
   19 |     rep(sz[a].size()) {
      |     ^~~
werewolf.cpp: In function 'void dfs(int)':
werewolf.cpp:5:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(n) for (int i=0; i<n; i++)
      |                              ~^~~~~~~~
    6 | const int c=200002;
      | ~~~~~~~~~~~~~~~~~~~            
    7 | int m, q, hely[c], mini[c][20], maxi[c][20], cnt;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    8 | vi sz[c], sol;
      | ~~~~~~~~~~~~~~                 
    9 | bool kis[c], nagy[c], v[c], jo;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   10 | void kdfs(int a, int b) {
      | ~~~~~~~~~~~~~~~~~~~~~~~~~      
   11 |     kis[a]=1;
      |     ~~~~~~~~~                  
   12 |     rep(sz[a].size()) {
      |     ~~~~~~~~~~~~~~~~~~~        
   13 |         int x=sz[a][i];
      |         ~~~~~~~~~~~~~~~        
   14 |         if (!kis[x] && x<=b) kdfs(x, b);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   15 |     }
      |     ~                          
   16 | }
      | ~                              
   17 | void ndfs(int a, int b) {
      | ~~~~~~~~~~~~~~~~~~~~~~~~~      
   18 |     nagy[a]=1;
      |     ~~~~~~~~~~                 
   19 |     rep(sz[a].size()) {
      |     ~~~~~~~~~~~~~~~~~~~        
   20 |         int x=sz[a][i];
      |         ~~~~~~~~~~~~~~~        
   21 |         if (!nagy[x] && x>=b) ndfs(x, b);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   22 |     }
      |     ~                          
   23 | }
      | ~                              
   24 | void dfs(int a) {
      | ~~~~~~~~~~~~~~~~~              
   25 |     v[a]=true, mini[cnt][0]=a, maxi[cnt][0]=a, hely[a]=cnt, cnt++;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   26 |     rep(sz[a].size()) {
      |     ~~~~~~~~~~~~~~~~           
werewolf.cpp:26:5: note: in expansion of macro 'rep'
   26 |     rep(sz[a].size()) {
      |     ^~~

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