제출 #748157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748157		Rafi22	기지국 (IOI20_stations)	C++14	100 / 100	920 ms	788 KiB

stations

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=1007;
vector<int>G[N];
int pre[N],post[N];
bool col[N];
int cnt;

void dfs(int v,int o)
{
    if(!col[v]) cnt++;
    pre[v]=cnt;
    for(auto u:G[v])
    {
        if(u==o) continue;
        col[u]=col[v]^1;
        dfs(u,v);
    }
    if(col[v]) cnt++;
    post[v]=cnt;
}

vector<int> label(int n,int k,vector<int>U,vector<int>V)
{
    cnt=0;
    for(int i=0;i<n;i++) G[i].clear();
    for(int i=0;i<n-1;i++)
    {
        G[U[i]].pb(V[i]);
        G[V[i]].pb(U[i]);
    }
    dfs(0,-1);
    vector<int>ans(n);
    for(int i=0;i<n;i++)
    {
        if(col[i]==0) ans[i]=pre[i];
        else ans[i]=post[i];
    }
    return ans;
}

int find_next_station(int s,int t,vector<int>c)
{
    int o=-1;
    bool color=0;
    for(auto u:c) if(u<s) color=1;
    if(s!=1)
    {
        if(color) o=c[0];
        else o=c.back();
    }
    if(color)
    {
        reverse(all(c));
        int R=s;
        for(auto u:c)
        {
            if(u==o) continue;
            if(u<=t&&t<=R) return u;
            R=u;
        }
    }
    else
    {
        int L=s;
        for(auto u:c)
        {
            if(u==o) continue;
            if(L<=t&&t<=u) return u;
            L=u;
        }
    }
    return o;
}

/*int main()
{
    vector<int>c=label(5,10,{0,1,1,2},{1,2,3,4});
    for(auto x:c) cout<<x<<endl;
    cout<<find_next_station(c[2], c[0],{c[4],c[1]})<<endl;
    cout<<find_next_station(c[1], c[3],{c[3],c[2],c[0]})<<endl;

    return 0;
}*/

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