| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 247385 | tqbfjotld | Lokahian Relics (FXCUP4_lokahia) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
int CollectRelics(int R1, int R2);
int FindBase(int N);
static void my_assert(int TF, const char* message){
if(!TF){ puts(message); exit(0); }
}
static int N, reach[202][202], call_cnt = 0;
int CollectRelics(int R1, int R2){
printf("called %d %d\n",R1,R2);
call_cnt++;
my_assert(call_cnt <= 300, "Wrong : Too Much Calls");
my_assert(0 <= R1 && 0 <= R2 && R1 < N && R2 < N && R1 != R2, "Wrong : Invalid Argument");
for(int i=0; i<N; i++){
if(reach[i][R1] && reach[i][R2]) {printf("returned %d\n",i);return i;}
}
printf("returned -1\n");
return -1;
}
int main(){
my_assert(scanf("%d", &N) == 1, "Error: Invalid Input");
my_assert(1 <= N && N <= 200, "Error: Invalid Input");
int con[202][202] = {0,};
for(int i = 1; i < N; i++){
int s, e, m;
my_assert(scanf("%d%d%d", &s, &e, &m) == 3, "Error: Invalid Input");
my_assert(0 <= s && s < N && 0 <= e && e < N && s != e && 1 <= m && m <= N, "Error: Invalid Input");
con[s][e] = con[e][s] = m;
}
int near[202];
for(int i = 0; i < N; i++){
memset(near, 0, sizeof(near));
reach[i][i] = 1, near[i] = -1;
for(int j = 0; j < N; j++){
if(con[i][j] > 0 && near[j] == 0) near[j] = con[i][j];
}
for(int vis = 1; vis < N; vis++){
int nxt = -1;
for(int j = 0; j < N; j++){
if(near[j] > 0 && near[j] <= vis){
nxt = j;
break;
}
}
if(nxt < 0) break;
reach[i][nxt] = 1, near[nxt] = -1;
for(int j = 0; j < N; j++){
if(con[nxt][j] > 0 && near[j] == 0) near[j] = con[nxt][j];
}
}
}
int base = FindBase(N);
printf("returned %d\n",base);
if(base == -1){
for(int i = 0; i < N; i++){
int cnt = 0;
for(int j = 0; j < N; j++) cnt += reach[i][j];
my_assert(cnt <= N / 2, "Wrong: Wrong Answer 1");
}
}
else if(0 <= base && base < N){
int cnt = 0;
for(int j = 0; j < N; j++) cnt += reach[base][j];
printf("can reach %d things\n",cnt);
my_assert(cnt > N / 2, "Wrong: Wrong Answer 2");
}
else my_assert(0, "Wrong: Wrong Answer 3");
printf("Correct\n%d\n", call_cnt);
return 0;
}
//#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
int NN;
vector<int> thing[205];
int qLim = 300;
int p[205];
int queried[205][205];
bool vis[205];
int root(int a){
return p[a]==a?a:p[a]=root(p[a]);
}
priority_queue<pair<pair<int,int>,int>,vector<pair<pair<int,int>,int> >,greater<pair<pair<int,int>,int> > > pq;
int sz[205];
int queryCount = 0;
int query(int a, int b){
if (queryCount>=qLim){
return -1;
}
if (a==b) return a;
if (a<0 || a>=NN || b<0 || b>=NN) return 1/0;
if (queried[a][b]!=-1) return queried[a][b];
int res = CollectRelics(a,b);
queryCount++;
if (res!=-1){
thing[res].push_back(a);
thing[res].push_back(b);
//printf("add edge %d %d, %d %d\n",res,a,res,b);
}
queried[a][b] = res;
queried[b][a] = res;
return res;
}
int dfs(int node){
vis[node] = true;
int res = 1;
for (auto x : thing[node]){
if (!vis[x]){
res += dfs(x);
}
}
return res;
}
int FindBase(int N){
memset(queried,-1,sizeof(queried));
NN = N;
if (N==1) return 0;
for (int x = 0; x<N; x++){
pq.push({{1,rand()},x});
p[x] = x;
}
int mn = -1;
vector<int> mns;
while (!pq.empty()){
if (pq.size()<2){
if (pq.size()==1) {mns.push_back(pq.top().second);pq.pop();}
continue;
}
auto a = pq.top();
pq.pop();
auto b = pq.top();
pq.pop();
int res = query(root(a.second),root(b.second));
if (res==-2) return -1;
if (res==-1){
}
else{
if (root(b.second)!=root(res)){
sz[root(res)] += sz[root(b.second)];
p[root(b.second)] = res;
}
if (root(a.second)!=root(res)){
sz[root(res)] += sz[root(a.second)];
p[root(a.second)] = res;
}
pq.push({{sz[root(res)],rand()},res});
}
}
vector<pair<int,int> > mn2;
for (int x = 0; x<N; x++){
mn2.push_back({sz[root(x)],x});
}
sort(mn2.begin(),mn2.end(),greater<pair<int,int> >());
int c = 0;
for (auto mnx : mn2){
int mn = mnx.second;
for (auto y : mn2){
int x = y.second;
if (root(x)!=root(mn)&&queryCount<qLim){
int res = query(root(x),root(mn));
if (res==-1) continue;
p[root(x)] = res;
p[root(mn)] = res;
}
}
}
for (int x = 0; x<N; x++){
for (int y = 0; y<N; y++){
vis[y] = false;
}
if (dfs(x)>N/2){
return x;
}
}
return -1;
}