# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
612053 | daria | 기지국 (IOI20_stations) | C++14 | 895 ms | 688 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"bits/stdc++.h"
#include "stations.h"
#include <vector>
using namespace std;
const int N = 2002;
int T;
vector<int> adj[N], lb(N);
vector<bool> vis(N);
void dfs(int s, bool b){ //b = 0 apertura, b = 1 chiusura
if(vis[s]) return;
vis[s] = 1;
if(!b) lb[s] = T; T++;
for(int u : adj[s]) dfs(u, 1-b);
if(b) lb[s] = T+N; T++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
for(int i=0; i<n; ++i) adj[i].clear();
lb.resize(n);
fill(lb.begin(), lb.end(), -1);
fill(vis.begin(), vis.end(), 0);
T = 0;
for(int i=0; i<n-1; ++i){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, 0);
//for(int i=0; i<n; ++i) cout << i << " " << lb[i] << endl;
return lb;
}
int find_next_station(int s, int t, vector<int> c) {
int par=-1;
if(s < N){ //s apertura
// le altre sono tutte chiusure
par = 0;
for(int u : c) par = max(par, u);
if(t < N){ //t apertura
if(t <= s) return par;
for(int i=0; i<c.size(); ++i) if(c[i] >= t+N) return c[i];
} else{ // t chiusura
if(t-N <= s) return par;
for(int i=0; i<c.size(); ++i) if(c[i] >= t) return c[i];
}
} else{ // s chiusura
// le altre sono tutte aperture
par = 400001;
for(int u : c) par = min(par, u);
if(t < N){ //t apertura
if(t+N >= s) return par;
for(int i=c.size()-1; i>=0; --i) if(c[i] <= t) return c[i];
} else{ // t chiusura
if(t+N <= s) return par;
for(int i=c.size()-1; i>=0; --i) if(c[i]+N <= t) return c[i];
}
}
return par;
}
/*
sai che t é stato visitato in un dato istante x; se tu sai che la tua é un’apertura e vale y:
se x < y allora devi salire a tuo padre
se x > y allora:
- o é un figlio —> per i figli controlli se la loro chiusura é avvenuta prima o dopo di x; se é vkavvenuta prima allora x é nel sottoalbero corrispondente
- altrimenti devi salire a tuo padre
per salire: il padre é quello con la chiusura più grande tra tutti i figli
*/
컴파일 시 표준 에러 (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... |