제출 #59544

#제출 시각아이디문제언어결과실행 시간메모리
59544WA_TLE게임 (IOI14_game)C++14
42 / 100
1046 ms17676 KiB
#include<deque> #include<queue> #include<vector> #include<algorithm> #include<iostream> #include<set> #include<cmath> #include<tuple> #include<string> #include<chrono> #include<functional> #include<iterator> #include<random> #include<unordered_set> #include<array> #include<map> #include<iomanip> #include<assert.h> #include<bitset> #include<stack> using namespace std; typedef long long int llint; typedef long double lldo; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase /* cout<<setprecision(20) cin.tie(0); ios::sync_with_stdio(false); */ const llint mod=998244353; const llint big=2.19e15+1; const long double pai=3.141592653589793238462643383279502884197; const long double eps=1e-15; template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;} template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;} llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);} llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;} template<class T> void SO(T& ve){sort(ve.begin(),ve.end());} template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());} template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();} template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();} #include"game.h" int n; int hen[1500][1500]={0};//直接の辺 -1->No 0->未定 1->想定解 2->Yes vector<vector<int>>kno;//可能性のある辺 mt19937 engine(13333); vector<int>rng; //O(n^2logn?) 自信がない //まずランダムな想定解を作る //想定解にかかってないなら無条件にNoを返していい //想定解にかかったなら想定解を変える vector<vector<int>>ki; void initialize(int in){ n=in; //uとvをランダムに置き換える rng.res(n); int i,j; for(i=0;i<n;i++){rng[i]=i;} shuffle(rng.begin(),rng.end(),engine); //想定解を作る vector<bool>use(n); use[0]=true; int gen=0,oto=1; ki.res(n); while(oto<n){ int ne=engine()%n; if(use[ne]){gen=ne;} else{ki[gen].pub(ne);ki[ne].pub(gen);hen[gen][ne]=1;hen[ne][gen]=1;gen=ne;use[ne]=1;oto++;} } kno.res(n); for(i=0;i<n;i++){ kno[i].res(n-1); for(j=1;j<n;j++){kno[i][j-1]=(i+j)%n;} } } int hasEdge(int u,int v){ int i,j; u=rng[u]; v=rng[v]; if(hen[u][v]==0){hen[u][v]=-1;hen[v][u]=-1;return 0;} vector<bool>doti(n); doti[u]=1; queue<int>que;que.push(u); while(que.size()>0){ int t=que.front();que.pop(); for(auto it:ki[t]){ if(doti[it]){continue;} if(it==v){continue;} doti[it]=1; que.push(it); } } vector<int>ulis; vector<int>vlis; for(i=0;i<n;i++){if(doti[i]){ulis.pub(i);}else{vlis.pub(i);}} shuffle(ulis.begin(),ulis.end(),engine); shuffle(vlis.begin(),vlis.end(),engine); if(ulis.size()<vlis.size()){ swap(ulis,vlis);swap(u,v); for(i=0;i<n;i++){doti[i]=(!doti[i]);} } int au=-1,av=-1; for(i=0;i<vlis.size();i++){ int t=vlis[i]; shuffle(kno[t].begin(),kno[t].end(),engine); for(j=0;j<kno[t].size();){ int it=kno[t][j]; if(t==v&&it==u){j++;continue;} if(hen[t][it]==-1){ kno[t][j]=kno[t].back(); kno[t].pob(); continue; } if(doti[it]){av=t;au=it;break;} j++; } if(au!=-1){break;} } if(au==-1){hen[u][v]=2;hen[v][u]=2;return 1;} hen[u][v]=-1;hen[v][u]=-1; hen[au][av]=-1;hen[av][au]=-1; for(i=0;i<ki[u].size();i++){ if(ki[u][i]==v){ki[u][i]=ki[u].back();ki[u].pob();} } for(i=0;i<ki[v].size();i++){ if(ki[v][i]==u){ki[v][i]=ki[v].back();ki[v].pob();} } ki[au].pub(av); ki[av].pub(au); return 0; }

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

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:113:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vlis.size();i++){
          ~^~~~~~~~~~~~
game.cpp:116:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<kno[t].size();){
           ~^~~~~~~~~~~~~~
game.cpp:132:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<ki[u].size();i++){
          ~^~~~~~~~~~~~~
game.cpp:135:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<ki[v].size();i++){
          ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...