Submission #599945

#TimeUsernameProblemLanguageResultExecution timeMemory
599945HanksburgerWerewolf (IOI18_werewolf)C++17
49 / 100
564 ms58484 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; int b[200005][18], c[200005][18], deg[200005], pos[200005], a[200005]; vector<int> adj[400005], ans; bool ok[400005]; queue<int> q; vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) { if (n<=3000 && x.size()<=6000 && s.size()<=3000) { for (int i=0; i<x.size(); i++) { adj[x[i]].push_back(y[i]); adj[y[i]].push_back(x[i]); adj[n+x[i]].push_back(n+y[i]); adj[n+y[i]].push_back(n+x[i]); } for (int i=0; i<n; i++) adj[i].push_back(n+i); for (int i=0; i<s.size(); i++) { for (int j=0; j<n*2; j++) ok[j]=0; ok[s[i]]=1; q.push(s[i]); while (!q.empty()) { int u=q.front(); q.pop(); for (int v:adj[u]) { if (!ok[v] && (v<n && v>=l[i] || v>=n && v<=n+r[i])) { ok[v]=1; q.push(v); } } } ans.push_back(ok[n+e[i]]); } return ans; } else { for (int i=0; i<x.size(); i++) { adj[x[i]].push_back(y[i]); adj[y[i]].push_back(x[i]); deg[x[i]]++; deg[y[i]]++; } for (int i=0; i<n; i++) { if (deg[i]==1) { a[0]=i; break; } } for (int i=0; i<=n-2; i++) { if (!i || adj[a[i]][0]!=a[i-1]) a[i+1]=adj[a[i]][0]; else a[i+1]=adj[a[i]][1]; pos[a[i+1]]=i+1; b[i][0]=min(a[i], a[i+1]); c[i][0]=max(a[i], a[i+1]); } for (int i=1; i<18; i++) { for (int j=0; j<=n-2; j++) { if (j+(1<<(i-1))<=n-2) { b[j][i]=min(b[j][i-1], b[j+(1<<(i-1))][i-1]); c[j][i]=max(c[j][i-1], c[j+(1<<(i-1))][i-1]); } else { b[j][i]=b[j][i-1]; c[j][i]=c[j][i-1]; } } } for (int i=0; i<s.size(); i++) { int u=pos[s[i]], v=pos[e[i]]; if (u<v) { int L=u, R=n-1; while (L<R) { int mid=(L+R+1)/2; int loog=log2(mid-L+0.1); if (min(b[L][loog], b[mid-(1<<loog)][loog])>=l[i]) L=mid; else R=mid-1; } if (v<=L) ans.push_back(1); else { int loog=log2(v-L+0.1); ans.push_back(max(c[L][loog], c[v-(1<<loog)][loog])<=r[i]); } } else { int L=0, R=u; while (L<R) { int mid=(L+R)/2; int loog=log2(R-mid+0.1); if (min(b[mid][loog], b[R-(1<<loog)][loog])>=l[i]) R=mid; else L=mid+1; } if (L<=v) ans.push_back(1); else { int loog=log2(L-v+0.1); ans.push_back(max(c[v][loog], c[L-(1<<loog)][loog])<=r[i]); } } } return ans; } }

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:12:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for (int i=0; i<x.size(); i++)
      |                       ~^~~~~~~~~
werewolf.cpp:21:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int i=0; i<s.size(); i++)
      |                       ~^~~~~~~~~
werewolf.cpp:33:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   33 |                     if (!ok[v] && (v<n && v>=l[i] || v>=n && v<=n+r[i]))
werewolf.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int i=0; i<x.size(); i++)
      |                       ~^~~~~~~~~
werewolf.cpp:87:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i=0; i<s.size(); i++)
      |                       ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...