# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
341709 | 2020-12-30T14:08:58 Z | ogibogi2004 | Stations (IOI20_stations) | C++14 | 857 ms | 1372 KB |
#include "stations.h" #include <vector> #include<bits/stdc++.h> using namespace std; #define time afds const int MAXN=1024; vector<int>g[MAXN]; int depth[MAXN]; int in_time[MAXN],out_time[MAXN],time=-1; void dfs(int u,int par) { in_time[u]=++time; for(auto v:g[u]) { if(v==par)continue; depth[v]=depth[u]+1; dfs(v,u); } out_time[u]=++time; } vector<int> label(int n, int k, vector<int> u, vector<int> v) { vector<int> labels(n); time=-1; memset(depth,-1,sizeof(depth)); for(int i=0;i<=n;i++)g[i].clear(); for(int i=0;i<u.size();i++) { g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } dfs(0,-1); set<int>l; map<int,int>mp; for (int i = 0; i < n; i++) { if(depth[i]%2==0) { labels[i]=in_time[i]; } else labels[i]=out_time[i]; l.insert(labels[i]); } int cnt=0; for(auto xd:l) { mp[xd]=cnt;++cnt; } for(int i=0;i<n;i++) { labels[i]=mp[labels[i]]; } return labels; } int find_next_station(int s, int t, vector<int> c) { if(c.size()==1)return c[0]; if(s<c[0]) { int in_s=s; int out_s=c[c.size()-1]+1; if(t<in_s||t>out_s)return c[c.size()-1]; else { int in1=s+1,out1; for(int i=0;i<c.size();i++) { out1=c[i]; if(t>=in1&&t<=out1)return c[i]; in1=out1+1; } } } else { int out_s=s; int in_s=c[1]-1; int in1,out1=out_s-1; //cout<<s<<" "<<t<<" "<<in_s<<" "<<out_s<<endl; if(t<in_s||t>out_s)return c[0]; for(int i=c.size()-1;i>0;i--) { in1=c[i]; if(t>=in1&&t<=out1)return c[i]; out1=in1-1; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 532 ms | 1372 KB | Wrong query response. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 538 ms | 816 KB | Wrong query response. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 630 ms | 992 KB | Wrong query response. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 857 ms | 816 KB | Output is correct |
2 | Correct | 779 ms | 1120 KB | Output is correct |
3 | Correct | 734 ms | 864 KB | Output is correct |
4 | Correct | 3 ms | 776 KB | Output is correct |
5 | Incorrect | 5 ms | 940 KB | Wrong query response. |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 607 ms | 1244 KB | Wrong query response. |
2 | Halted | 0 ms | 0 KB | - |