제출 #578644

#제출 시각아이디문제언어결과실행 시간메모리
578644perchuts기지국 (IOI20_stations)C++17
39 / 100
974 ms772 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define sz(x) (int) x.size() #define endl '\n' #define pb push_back #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); using namespace std; using ll = long long; using ull = unsigned long long; using ii = pair<int,int>; using iii = tuple<int,int,int>; const int inf = 2e9+1; const int mod = 1e9+7; const int maxn = 1e5+100; template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; } template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; } #include "stations.h" vector<int>g[1001], labels; int t = 0; void dfs(int u,int p,bool entrada){ if(entrada){ labels[u] = t++; } for(auto v:g[u]){ if(v==p)continue; dfs(v,u,entrada^1); } if(!entrada){ labels[u] = t++; } } vector<int> label(int n, int k, vector<int> u, vector<int> v) { for(int i=0;i<n;++i){ g[i].clear(); } t = 0; for(int i=0;i<n-1;++i){ g[u[i]].pb(v[i]); g[v[i]].pb(u[i]); } labels.resize(n); dfs(0,0,1); return labels; } int find_next_station(int s, int t, vector<int> c) { int m = sz(c); if(c[lower_bound(all(c),t)-begin(c)]==t)return t;//sou vizinho if(s>c[m-1]){//sou uma saida if(t>s||t<c[0])return c[0];//fora da subarvore return c[lower_bound(all(c),t) - begin(c) - 1];//ultimo cara que é menor }else{//sou uma entrada if(t>c[m-1]||t<s)return c[m-1];//fora da subarvore return c[lower_bound(all(c),t) - begin(c)];//primeiro cara que é maior } } // int main(){_ // int n;cin>>n; // vector<int>u(n-1),v(n-1); // for(int i=0;i<n-1;++i){ // cin>>u[i]>>v[i]; // } // vector<int>labels = label(n,n-1,u,v); // // for(int i=1;i<=n;++i)printf("%d: %d\n",i-1,labels[i-1]); // cout<<find_next_station(1,3,{2,4})<<endl; // }
#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...