제출 #805986

#제출 시각아이디문제언어결과실행 시간메모리
805986LIF늑대인간 (IOI18_werewolf)C++14
49 / 100
879 ms72684 KiB
#include "werewolf.h" #include<vector> #include<bits/stdc++.h> #include<queue> using namespace std; int pos[300005]; int ind[300005]; int id[300005]; int val[300005]; vector<int> ans; vector<int> vv[300005]; int stmin[200005][23]; int stmax[200005][23]; bool flag1[400005]; bool vis[300005]; bool flag2[300005]; bool vis2[30005]; void dfs(int now,int num) { //cout<<now<<" "<<num<<endl; vis[now] = true; id[now] = num; val[num] = now; for(int i=0;i<vv[now].size();i++) { int to = vv[now][i]; if(vis[to] == false)dfs(to,num+1); } return; } int checkmin(int x,int y) { int len = log(y-x+1) / log(2); return min(stmin[x][len],stmin[y-(1<<(len))+1][len]); } int checkmax(int x,int y) { int len = log(y-x+1) / log(2); return max(stmax[x][len],stmax[y-(1<<(len))+1][len]); } 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) { if(N <= 3000) { for(int i=0;i<X.size();i++) { vv[X[i]].push_back(Y[i]); vv[Y[i]].push_back(X[i]); } for(int i=0;i<S.size();i++) { queue<int> q; for(int j=0;j<N;j++)flag1[j] = false; for(int j=0;j<N;j++)flag2[j] = false; for(int j=0;j<N;j++)vis[j] = false; for(int j=0;j<N;j++)vis2[j] = false; q.push(S[i]); flag1[S[i]] = true; while(q.empty() == false) { //cout<<"yeah"<<endl; int xx = q.front(); q.pop(); if(vis[xx] == true)continue; vis[xx] = true; for(int j=0;j<vv[xx].size();j++) { int to = vv[xx][j]; if(to >= L[i]) { flag1[to] = true; // vis[to] = true; q.push(to); } } } //cout<<"YEAH"<<endl; q.push(E[i]); flag2 [E[i]] = true; while(q.empty() == false) { int xx = q.front(); q.pop(); //cout<<xx<<endl; if(vis2[xx] == true)continue; vis2[xx] = true; for(int j=0;j<vv[xx].size();j++) { int to = vv[xx][j]; if(to <= R[i]) { flag2[to] = true; q.push(to); } } } for(int j=0;j<N;j++) { if(flag1[j] == true && flag2[j] == true && L[i] <= j && j <= R[i]) { ans.push_back(1); break; } } if(ans.size() < i+1)ans.push_back(0); } return ans; } else { for(int i=0;i<X.size();i++) { ind[X[i]]++;ind[Y[i]]++; vv[X[i]].push_back(Y[i]); vv[Y[i]].push_back(X[i]); } //cout<<"yeah"<<endl; for(int i=0;i<N;i++) { if(ind[i] != 1)continue; dfs(i,0); break; } for(int i=0;i<N;i++) { stmin[i][0] = val[i]; stmax[i][0] = val[i]; } for(int i=1;i<=20;i++) { for(int j=0;j+ (1<<i) - 1< N;j++) { stmin[j][i] = min(stmin[j][i-1],stmin[j+(1<<(i-1))][i-1]); stmax[j][i] = max(stmax[j][i-1],stmax[j+(1<<(i-1))][i-1]); } } /*for(int i=0;i<N;i++)cout<<i<<" "; cout<<endl;; for(int i=0;i<N;i++)cout<<id[i]<<" "; cout<<endl; for(int i=0;i<N;i++)cout<<val[i]<<" "; cout<<endl;*/ // cout<<checkmax(1,5)<<endl; for(int i=0;i<S.size();i++) { int xx = id[S[i]]; int yy = id[E[i]]; if(xx < yy) { int ll = xx;int rr = yy; int last1 = xx; int last2 = yy; while(ll <= rr) { int mid = (ll+rr)>>1; if(checkmin(xx,mid) >= L[i]) { last1 = mid; ll = mid + 1; } else rr = mid - 1; } ll = xx;rr = yy; while(ll <= rr) { int mid = (ll+rr)>>1; if(checkmax(mid,yy) <= R[i]) { last2 = mid; rr = mid - 1; } else ll = mid+1; } if(last1 >= last2)ans.push_back(1); else ans.push_back(0); // cout<<last1<<" "<<last2<<endl; } else { swap(xx,yy); int ll = xx;int rr = yy; int last1 = xx; int last2 = yy; while(ll <= rr) { int mid = (ll+rr)>>1; if(checkmax(xx,mid) <= R[i]) { last1 = mid; ll = mid + 1; } else rr = mid - 1; } ll = xx;rr = yy; while(ll <= rr) { int mid = (ll+rr)>>1; if(checkmin(mid,yy) >= L[i]) { last2 = mid; rr = mid - 1; } else ll = mid+1; } if(last1 >= last2)ans.push_back(1); else ans.push_back(0); } } return ans; } }

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0;i<vv[now].size();i++)
      |              ~^~~~~~~~~~~~~~~
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:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<X.size();i++)
      |               ~^~~~~~~~~
werewolf.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<S.size();i++)
      |               ~^~~~~~~~~
werewolf.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int j=0;j<vv[xx].size();j++)
      |                 ~^~~~~~~~~~~~~~
werewolf.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int j=0;j<vv[xx].size();j++)
      |                 ~^~~~~~~~~~~~~~
werewolf.cpp:107:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |    if(ans.size() < i+1)ans.push_back(0);
      |       ~~~~~~~~~~~^~~~~
werewolf.cpp:113:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |    for(int i=0;i<X.size();i++)
      |                ~^~~~~~~~~
werewolf.cpp:146:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   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...