| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 377362 | Thistle | 카니발 티켓 (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "plants.h"
#include <vector>
#include<algorithm>
#include<set>
#include<iostream>
#include<random>
#include<queue>
using namespace std;
using ll=long long;
using H=pair<ll, ll>;
#define vec vector
#define vi vec<ll>
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),0,(n))
#define siz(a) int((a).size())
int n;
vec<vec<int>>e;
void init(int k, std::vector<int> r) {
//DAG kouchiku
n=siz(r);
rep(i,n) r.pb(r[i]);
e.assign(n,vec<int>());
rep(i,n)rep(_,n){
if(i==_) continue;
int j=_;
if(j<i) j+=n;
if(i+k<=j) continue;
int t=j-i,mn,mx;
if(j+k<=i+n){
mn=max(0,r[j]-t)+1;
mx=k-1;
}
else{
int step=i+k-j-1;
mx=k-1;
mn=max(0,(r[j]-(k-(2*step+2))))+1;
}
if(r[i]<mn||mx<r[i]){
e[_].pb(i);
}
if(j+k<=i+n){
mx=t-1+max(0,r[j]-t);
mn=0;
}
else{
int step=i+k-j-1;
mn=0;
mx=n-k+min(2*step, r[j]-1);
}
if(r[i]<mn||mx<r[i]){
e[i].pb(_);
}
}
return;
}
int compare_plants(int x, int y) {
x--;y--;
vec<bool>used(n,0);
queue<int>q;
q.push(x);
used[x]=1;
while(!q.empty()){
int t=q.front();q.pop();
for(auto g:e[t]){
if(!used[g]){
used[g]=1;
q.push(g);
}
}
}
if(used[y]) return -1;
used=vec<bool>(n,0);
used[y]=1;
q.push(y);
while(!q.empty()){
int t=q.front();q.pop();
for(auto g:e[t]){
if(!used[g]){
used[g]=1;
q.push(g);
}
}
}
if(used[x]) return 1;
return 0;
}