Submission #321871

#	Time	Username	Problem	Language	Result	Execution time	Memory
321871		akobi	Stations (IOI20_stations)	C++14	100 / 100	1097 ms	1248 KiB

stations

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
    vector< vector<int> > edge;
    vector<int> t,p,fix,anss;
    vector< pair<int,int> >ans;
    for (int i=0; i<n; i++)
    {
        edge.pb(t);
        p.pb(0);
        fix.pb(0);
        anss.pb(0);
    }
    for (int i=0; i<n-1; i++)
    {
        edge[u[i]].pb(v[i]);
        edge[v[i]].pb(u[i]);
    }
    p[0]=-1;
    int c=0,cnt=0,l=0;
    while (c>=0)
    {
        int inn=0,out=0,bbb=0;
        if (fix[c]==0)
        {
            inn=cnt++;
            if (!l)
            {
                ans.pb(mp(inn,c));
                // cout<<inn<<" "<<c<<endl;
            } 
        }
        fix[c]=1;
        for (int i=0; i<(int)(edge[c].size()); i++)
        {
            if (edge[c][i]!=p[c] && fix[ edge[c][i] ]==0)
            {
                p[ edge[c][i] ]=c;
                c=edge[c][i];
                bbb=1;
                break;
            }
        }
        if (bbb)
        {
            l=(l+1)%2;
            continue;
        }
        out=cnt++;
        if (l)
        {
            ans.pb(mp(out,c));
            // cout<<out<<" "<<c<<endl;
        }
        c=p[c];
        l=(l+1)%2;
    }
    sort(ans.begin(),ans.end());
    for (int i=0; i<n; i++)
        anss[ans[i].S]=i;
    return anss;
}
int find_next_station(int s, int t, vector<int> c)
{
    if (s<c[0])
    {
        //in
        if (t<s || t>c[c.size()-2])
            return c[c.size()-1];
        for (int i=0; i<(int)(c.size())-1; i++)
            if (t<=c[i])
                return c[i];
    }
    else
    {
        //out
        if (t>s || t<c[1])
            return c[0];
        for (int i=1; i<(int)(c.size())-1; i++)
            if (t<c[i+1])
                return c[i];
        return c[c.size()-1];
    }
    return -1;
}
// int n,k,a,b;
// vector<int> u,v,ans;
// int main()
// {
//     cin>>n>>k;
//     for (int i=0; i<n-1; i++)
//     {
//         cin>>a>>b;
//         u.pb(a);
//         v.pb(b);
//     }
//     ans=label(n,k,u,v);
//     for (int i=0; i<n; i++)
//         cout<<ans[i]<<" ";
//     cout<<endl;
//     return 0;
// }

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