Submission #525396

#TimeUsernameProblemLanguageResultExecution timeMemory
525396idasStations (IOI20_stations)C++17
100 / 100
994 ms772 KiB
#include <bits/stdc++.h> #define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr) #define FOR(i, begin, end) for(int i = (begin); i < (end); i++) #define TSTS int ttt; cin >> ttt; while(ttt--) solve() #define all(x) (x).begin(), (x).end() #define le(vec) vec[vec.size()-1] #define sz(x) ((int)((x).size())) #define pb push_back #define s second #define f first using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef map<int, int> mii; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef pair<long double, long double> pdd; const int INF=1e9, MOD=1e9+7, mod=998244353; const ll LINF=1e18; void setIO() { FAST_IO; } void setIO(string s) { FAST_IO; freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); } const int N=1e3+10; int dp[N], lb[N], lst; bool v[N]; vi ad[N]; void build(int u, int pst) { for(auto x : ad[u]){ if(x==pst) continue; build(x, u); dp[u]+=dp[x]; } dp[u]++; } void dfs(int u, int pst, bool mx) { if(mx){ while(v[lst]) lst--; lb[u]=lst; v[lst]=true; } for(auto x : ad[u]){ if(x==pst) continue; if(mx){ int now=lb[u]; while(v[now]) now--; lb[x]=now-dp[x]+1; assert(!v[lb[x]]); v[lb[x]]=true; } dfs(x, u, !mx); } } vi label(int n, int k, vi uu, vi vv) { FOR(i, 0, n+1) ad[i].clear(), v[i]=false, dp[i]=0, lb[i]=0; FOR(i, 0, n-1) { ad[uu[i]].pb(vv[i]); ad[vv[i]].pb(uu[i]); } lst=n; build(0, -1); dfs(0, -1, true); vi ans; FOR(i, 0, n) ans.pb(lb[i]); return ans; } int find_next_station(int s, int t, vi c) { for(auto x : c){ if(x==t){ return t; } } if(s<c[0]){ if(t<s){ return le(c); } FOR(i, 0, sz(c)-1) { if(c[i]>t){ return c[i]; } } return le(c); } else{ if(t>s){ return c[0]; } for(int i=sz(c)-1; i>0; i--){ if(c[i]<t){ return c[i]; } } return c[0]; } } /*int main() { setIO(); /*int nn, kk; cin >> nn >> kk; vi ar(nn-1), br(nn-1); FOR(i, 0, nn-1) { cin >> ar[i] >> br[i]; } for(auto x : label(nn, kk, ar, br)){ cout << x << '\n'; }*/ //cout << find_next_station(3, 4, {1,2}); //}

Compilation message (stderr)

stations.cpp:123:5: warning: "/*" within comment [-Wcomment]
  123 |     /*int nn, kk; cin >> nn >> kk;
      |      
stations.cpp: In function 'void setIO(std::string)':
stations.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
stations.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...