Submission #311951

#	Time	Username	Problem	Language	Result	Execution time	Memory
311951		MonkeyKing	Stations (IOI20_stations)	C++14	0 / 100	2396 ms	2097156 KiB

stations

#ifndef _SELF_UTILITY
#define _SELF_UTILITY 1
#include <numeric>
#include "stations.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#include <time.h>
#define Endl endl
#define mp make_pair
#define ll long long 
#define ull unsigned long long
#define pii pair<int,int>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define quickcin ios_base::sync_with_stdio(false);
#ifdef __TAKE_CONTROL_OF_MOD
int mod;
#else
const int mod=1e9+7;
#endif
const int gmod=2;
const int inf=1039074182;
const double eps=1e-9;
const ll llinf=1LL*inf*inf;
template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;}
template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;}
inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31 & mod);}
template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;}
template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;}
template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;}
template <typename T> inline T mabs(T x) {return (x<0?-x:x);}
#endif
using namespace std;
using namespace std;
vector <int> edges[1005];

void dfs(int x,int depth,int par,vector <int> &res)
{
    static int dfn=0;
    if(depth & 1)
    {
        res[x]=dfn++;
        for(auto u:edges[x])
        {
            if(u==par) continue;
            dfs(u,depth+1,x,res);
        }
    }
    else
    {
        for(auto u:edges[x])
        {
            if(u==par) continue;
            dfs(u,depth+1,x,res);
        }
        res[x]=dfn++;
    }
}

vector <int> label(int n,int k,vector <int> _ea,vector <int> _eb)
{
    vector <int> res;
    res.resize(n);
    for(int i=0;i<n-1;i++)
    {
        edges[_ea[i]].push_back(_eb[i]);
        edges[_eb[i]].push_back(_ea[i]);
    }
    dfs(0,0,-1,res);
    return res;
}

int find_next_station(int s,int t,vector <int> c)
{
    if(s>c[0]) // 后根
    {
        sort(all(c));
        int par=*c.begin();
        c.erase(c.begin());
        if(c.empty()) return par;
        if(t<c.front() || t>=s) return par;
        reverse(all(c));
        for(auto x:c)
        {
            if(t>=x) return x;
        }
    }
    else // 先根
    {
        sort(all(c));
        int par=*(--c.end());
        c.erase(--c.end());
        if(c.empty()) return par;
        if(t>c.back() || t<=s) return par;
        for(auto x:c)
        {
            if(t<=x) return x;
        }
    }
    assert(false);
    return -1;
}

// #include <self/debug>
// int main()
// {
//     // vector <int> v=label(5,10,{0,1,1,2},{1,2,3,4});
//     // cout<<v<<endl;
//     // cout<<find_next_station(0,1,{4,2,3})<<endl;
//     return 0;
// }

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