Submission #292115

#TimeUsernameProblemLanguageResultExecution timeMemory
292115FashoWerewolf (IOI18_werewolf)C++14
34 / 100
638 ms61036 KiB
#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()) {
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...