| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1116946 | alecurse | Speedrun (RMI21_speedrun) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "speedrun.h"
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int> > adj;
vector<pair<int,int> > hints;
stack<int> s;
int root=1;
void dfs(int x, int e) {
if(adj[x].size()==1&&x!=root) {
hints[x].first=s.top();
s.pop();
return;
}
if(adj[x][0]==e) {
hints[x].first=adj[x][1];
} else {
hints[x].first=adj[x][0];
}
for(int i=adj[x].size()-1;i>0;i--) {
if(adj[x][i]==e)
continue;
s.push(adj[x][i]);
}
for(auto b : adj[x]) {
if(b==e) continue;
hints[b].second=x;
dfs(b,x);
}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
adj.resize(N+1);
hints.resize(N+1);
for(int i=0;i<N-1;i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
for(int i=1;i<=N;i++) {
if(adj[i].size()==1) {
root=i;
break;
}
}
dfs(root,-1);
setHintLen(20);
for(int i=1;i<=N;i++) {
for(int j=0;j<10;j++) {
if((hints[i].first&(1<<j))!=0) {
setHint(i,j+1,1);
} else {
setHint(i,j+1,0);
}
}
for(int j=0;j<10;j++) {
if((hints[i].second&(1<<j))!=0) {
setHint(i,j+11,1);
} else {
setHint(i,j+11,0);
}
}
}
}
int getparent(int x) {
int res=0;
for(int i=0;i<10;i++) {
if(getHint(i+11)) {
res|=(1<<i);
}
}
return res;
}
int getchild(int x) {
int res=0;
for(int i=0;i<10;i++) {
if(getHint(i+1)) {
res|=(1<<i);
}
}
return res;
}
void speedrun(int subtask, int N, int start) { /* your solution here */
int sospeso=-1;
vector<bool> vis(N+1);
vector<int> childs(N+1);
vector<int> parents(N+1);
int nodo=start;
while(true) {
vis[nodo]=true;
childs[nodo]=getchild(nodo);
parents[nodo]=getparent(nodo);
if(vis[childs[nodo]]||childs[nodo]==0) {
if(sospeso!=-1) {
bool th = goTo(sospeso);
if(th) {
nodo = sospeso;
} else {
th = goTo(parents[nodo]);
nodo = parents[nodo];
}
} else if(!vis[parents[nodo]]&&parents[nodo]!=0) {
bool th = goTo(parents[nodo]);
nodo = parents[nodo];
} else {
break;
}
} else {
bool th = goTo(childs[nodo]);
if(th) {
nodo = childs[nodo];
} else {
sospeso=childs[nodo];
if(parents[nodo]==0)
break;
th = goTo(parents[nodo]);
nodo = parents[nodo];
}
}
}
}