Submission #338058

#	Time	Username	Problem	Language	Result	Execution time	Memory
338058		MvC	Stations (IOI20_stations)	C++17	100 / 100	1017 ms	1244 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e3+50;
const ll mod=1e9+7;
using namespace std;
int i,d[nmax],in[nmax],out[nmax],tt;
vector<int>g[nmax],rs;
void dfs(int x,int p)
{
    d[x]=d[p]^1;
    if(d[x])in[x]=tt++;
    for(int i=0;i<lun(g[x]);i++)if(g[x][i]!=p)dfs(g[x][i],x);
    if(!d[x])out[x]=tt++;
}
vector<int> label(int n,int k,vector<int> u,vector<int> v)
{
    rs.clear();
    for(i=0;i<n;i++)
    {
        g[i].clear();
        d[i]=0;
    }
    tt=0;
    for(i=0;i<n-1;i++)
    {
        g[u[i]].pb(v[i]);
        g[v[i]].pb(u[i]);
    }
    dfs(0,0);
    for(i=0;i<n;i++)
    {
        if(d[i])rs.pb(in[i]);
        else rs.pb(out[i]);
    }
    return rs;
}
int find_next_station(int s,int t,vector<int> c)
{
    sort(all(c));
    int k=lun(c);
    if(s>c.back())
    {
        for(i=1;i<k-1;i++)if(t>=c[i] && t<c[i+1])return c[i];
        if(t>=c[k-1] && t<s)return c[k-1];
        return c[0];
    }
    else
    {
        for(i=k-2;i>=1;i--)if(t>c[i-1] && t<=c[i])return c[i];
        if(t>s && t<=c[0])return c[0];
        return c.back();
    }
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);

    return 0;
}*/

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 61 / 61