제출 #294500

#제출 시각아이디문제언어결과실행 시간메모리
294500Hemimor게임 (IOI14_game)C++14
42 / 100
1078 ms4596 KiB
#include "game.h" #include <algorithm> #include <iostream> #include <iomanip> #include <numeric> #include <cassert> #include <random> #include <vector> #include <cmath> #include <queue> #include <set> #include <map> #define syosu(x) fixed<<setprecision(x) using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> P; typedef pair<double,double> pdd; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<double> vd; typedef vector<vd> vvd; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<string> vs; typedef vector<P> vp; typedef vector<vp> vvp; typedef vector<pll> vpll; typedef pair<P,int> pip; typedef vector<pip> vip; const int inf=1<<30; const ll INF=1ll<<60; const double pi=acos(-1); const double eps=1e-8; const ll mod=1e9+7; const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}; class Union_Find_Tree{ public: vi p,r,s; Union_Find_Tree(int n){ p=r=vi(n); s=vi(n,1); for(int i=0;i<n;i++) p[i]=i; } int Par(int x){ if(p[x]==x) return x; return p[x]=Par(p[x]); } int Size(int x){return s[Par(x)];} bool Unite(int x,int y){ x=Par(x); y=Par(y); if(x==y) return 0; if(r[x]<r[y]){ p[x]=y; s[y]+=s[x]; } else{ p[y]=x; s[x]+=s[y]; if(r[x]==r[y]) r[x]++; } return 1; } bool Same(int x,int y){return Par(x)==Par(y);} }; int N; vvi g,G; vi b; void initialize(int n){ N=n; Union_Find_Tree uft(n); g=vvi(n,vi(n)); G=vvi(n,vi(n,1)); b=vi(n); vp a; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) a.push_back({i,j}); mt19937 rnd(1001); shuffle(a.begin(),a.end(),rnd); for(auto p:a){ int u=p.first,v=p.second; if(uft.Unite(u,v)) g[u][v]=g[v][u]=1; } } void dfs(int v,int t,vi &c){ b[v]=t; c.push_back(v); for(int u=0;u<N;u++) if(g[v][u]&&b[u]!=t) dfs(u,t,c); } int hasEdge(int u,int v){ G[u][v]=G[v][u]=0; if(!g[u][v]) return 0; fill(b.begin(),b.end(),0); g[u][v]=g[v][u]=0; vi c,d; dfs(u,1,c); dfs(v,-1,d); for(auto i:c) for(auto j:d) if(G[i][j]){ g[i][j]=g[j][i]=1; return 0; } return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...