# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
802403 | I_Love_EliskaM_ | 기지국 (IOI20_stations) | C++14 | 580 ms | 788 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
const int N=1e3;
int l[N], r[N];
vector<int> adj[N];
int nxt=0;
void dfs(int u, int p) {
l[u]=r[u]=nxt++;
for(auto&v:adj[u]) {
if (v==p) continue;
dfs(v,u);
r[u]=max(r[u],r[v]);
}
}
vector<int> label(int n, int k, vector<int>u, vector<int> v) {
forn(i,n) adj[i].clear(); nxt=0;
forn(i,n-1) {
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
}
int mx=0;
forn(i,n) mx=max(mx,(int)adj[i].size());
if (mx==2) {
forn(i,n) {
if (adj[i].size()==1) {
dfs(i,-1);
break;
}
}
vector<int> z(n); forn(i,n) z[i]=l[i];
return z;
}
int zzz=1;
forn(i,n-1) {
zzz&=(u[i]==i+1 && v[i]==i/2) || (u[i]==i/2 && v[i]==i+1);
}
if (zzz) {
vector<int> z(n);
forn(i,n) z[i]=i;
return z;
}
dfs(0,-1);
vector<int> ans(n);
forn(i,n) ans[i]=l[i]+N*r[i];
return ans;
}
bitset<N> can[N];
void dfs(int u) {
can[u][u]=1;
if (2*u+1 < N) {
dfs(2*u+1);
can[u]|=can[2*u+1];
}
if (2*u+2 < N) {
dfs(2*u+2);
can[u]|=can[2*u+2];
}
}
int called=1;
int find_next_station(int s, int t, vector<int> adj) {
if (adj.size()==1) return adj[0];
//if (adj.size()==2) {
// if (adj[0]==s-1 && adj[1]==s+1) {
// if (s<t) return adj[1];
// else return adj[0];
// }
//}
if (called) {
dfs(0);
called=0;
}
if (max(s,t)<N) {
if (can[s][t]) {
if (can[2*s+1][t]) return 2*s+1;
else return 2*s+2;
} else return (s-1)/2;
}
int l=s%N, r=s/N;
int lx=t%N, rx=t/N;
if (l<=lx && rx<=r) {
for(auto&x:adj) {
int lq=x%N, rq=x/N;
if (lq<l) continue;
if (lq<=lx && rx<=rq) return x;
}
} else {
for(auto&x:adj) {
int lq=x%N, rq=x/N;
if (lq<l) return x;
}
}
//assert(0);
exit(1);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |