제출 #536886

#제출 시각아이디문제언어결과실행 시간메모리
536886dantoh000Speedrun (RMI21_speedrun)C++14
21 / 100
102 ms4760 KiB
#include "speedrun.h" #include <bits/stdc++.h> using namespace std; int arr1[1005][1005]; int arr2[1005][25]; vector<int> G[1005]; void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */ if (subtask == 1){ for (int i = 1; i < N; i++){ arr1[A[i]][B[i]] = arr1[B[i]][A[i]] = 1; } setHintLen(N); for (int i = 1; i <= N; i++){ for (int j = 1; j <= N; j++){ if (arr1[i][j]) setHint(i,j,1); } } } if (subtask == 2){ setHintLen(20); int ct[N]; for (int i = 1; i < N; i++){ ct[A[i]]++; ct[B[i]]++; } int x = 0; for (int i = 1; i <= N; i++){ if (ct[i] == N-1) x = i; } for (int i = 1; i <= N; i++){ for (int j = 1; j <= 20; j++){ if ((x>>(j-1))&1) setHint(i,j,1); } } } if (subtask == 3){ setHintLen(20); for (int i = 1; i < N; i++){ G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); } for (int i = 1; i <= N; i++){ for (int j = 1; j <= 10; j++){ if ((G[i][0]>>(j-1))&1) setHint(i,j,1); } if (G[i].size() == 1) continue; for (int j = 11; j <= 20; j++){ if ((G[i][1]>>(j-11))&1) setHint(i,j,1); } } } } int n; vector<int> G1[1005]; vector<int> G3[1005]; void getG1(int u){ for (int i = 1; i <= n; i++){ if (getHint(i)){ G1[u].push_back(i); } } } void getG3(int u){ int x = 0; for (int i = 1; i <= 10; i++){ if (getHint(i)) x += (1<<(i-1)); } G3[u].push_back(x); x = 0; for (int i = 11; i <= 20; i++){ if (getHint(i)) x += (1<<(i-11)); } if (x) { G3[u].push_back(x); } } void dfs1(int u, int p){ getG1(u); for (auto v : G1[u]){ if (v == p) continue; goTo(v); dfs1(v, u); } if (p != -1) goTo(p); } void dfs3(int u, int p){ //printf("at %d\n",u); getG3(u); for (auto v : G3[u]){ if (v == p) continue; printf("%d %d\n",u,v); goTo(v); dfs3(v, u); } if (p != -1) goTo(p); } void speedrun(int subtask, int N, int start) { /* your solution here */ n = N; if (subtask == 1){ dfs1(start, -1); } if (subtask == 2){ int x = 0; for (int i = 1; i <= 20; i++){ if (getHint(i)) x += (1<<(i-1)); } //printf("%d", x); if (start != x) goTo(x); for (int i = 1; i <= N; i++){ if (i != x){ goTo(i); goTo(x); } } } if (subtask == 3){ dfs3(start, -1); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...