| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 923270 | 2024-02-07T04:29:43 Z | MinhAnhnd | Speedrun (RMI21_speedrun) | C++14 | 0 ms | 0 KB |
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
bool leaf[N+1];
bool visited[N+1];
long parent[N+1];
long first_val[N+1];
long second_val[N+1];
long depth[N+1];
stack<long> tovisit;
setHintLen(20);
vector<long> adjlist[N+1];
vector<long> leaves;
for (int i = 1;i<=N;i++){
leaf[i] = 1;
parent[i] = 0;
visited[i] = 0;
first_val[i] = -1;
second_val[i] = -1;
depth [i]= 0;
}
//setHintLen(N);
for(int i = 1;i<N;i++){
adjlist[A[i]].push_back(B[i]);
adjlist[B[i]].push_back(A[i]);
}
tovisit.push(1);
depth[1] = 1;
while(!tovisit.empty()){
long current = tovisit.top();
tovisit.pop();
if(visited[current]) continue;
visited[current]=1;
for (auto i:adjlist[current]){
if(!visited[i]){
depth[i] = depth[current] + 1;
leaf[current] = 0;
parent[i] = current;
tovisit.push(i);
}
}
}
for (int i = 1;i<=N;i++){
if (leaf[i]){
leaves.push_back(i);
}
}
for (auto green: leaves){
if (second_val[parent[green]]==-1) second_val[parent[green]] = green;
current = parent[green];
while(current!=0){
first_val[current] = parent[current];
if (second_val[parent[current]]==-1) second_val[parent[current]] = current;
current = parent[current];
}
}
leaves.push_back(leaves[0]);
for (int i = 1;i<leaves.size();i++){
long a = leaves[i-1];
long b = leaves[i];
long b_low = 0;
while(depth[a]>depth[b]) a= parent[a];
while(depth[a]<depth[b]) {b= parent[b];b_low=b;}
while(a!=b){
a= parent[a];
b= parent[b];b_low=b;
}
first_val[leaves[i-1]] = b;
second_val[leaves[i-1]] = b_low;
}
for (long i = 1;i<=N;i++){
for (long j = 0;j<=9;j++) setHint(i,j+1,(first_val[i]>>j)&1);
for (long j = 0;j<=9;j++) setHint(i,j+11,(second_val[i]>>j)&1);
}
}
void speedrun(int subtask, int N, int start) { /* your solution here */
}