Submission #706465

#	Time	Username	Problem	Language	Result	Execution time	Memory
706465		ToroTN	Stations (IOI20_stations)	C++14	0 / 100	884 ms	676 KiB

stations

#include<bits/stdc++.h>
using namespace std;
#include "stations.h"
//#include "stub.cpp"
#include <vector>
#define pb push_back
vector<int> adj[1005];
set<int> ss;
map<int,int> mp;
int st[1005],ed[1005],tim=0,lv[1005],pack[1005],cnt;
void dfs(int u,int p)
{
    st[u]=++tim;
    for(auto node:adj[u])
    {
        if(node==p)continue;
        lv[node]=1-lv[u];
        dfs(node,u);
    }
    ed[u]=++tim;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
    for(int i=1;i<=n;i++)adj[i].clear();
    ss.clear();
    mp.clear();
	for (int i = 0; i < n-1; i++) 
    {
        adj[u[i]+1].pb(v[i]+1);
        adj[v[i]+1].pb(u[i]+1);
	}
    lv[1]=0;
    dfs(1,1);
    for(int i=1;i<=n;i++)
    {
        if(lv[i]==0)
        {
            pack[i]=st[i];
        }else
        {
            pack[i]=ed[i];
        }
    }
    for(int i=1;i<=n;i++)ss.insert(pack[i]);
    cnt=0;
    for(auto it=ss.begin();it!=ss.end();it++)
    {
        mp[(*it)]=cnt;
        ++cnt;
    }
    for(int i=1;i<=n;i++)pack[i]=mp[pack[i]];
    labels.clear();
    for(int i=0;i<n;i++)labels.pb(pack[i+1]);
    /*for(int i=1;i<=n;i++)
    {
        printf("%d\n",i);
        for(auto node:adj[i])
        {
            printf("%d ",node);
        }
        printf("\n");
    }*/
    /*for(int i=0;i<labels.size();i++)
    {
        printf("%d ",labels[i]);
    }
    printf("\n");*/
    return labels; 
}

int find_next_station(int s, int t, std::vector<int> c) 
{
    //printf("hk\n");
    //printf("s=%d t=%d\n",s,t);
    //printf("adj\n");
    /*for(auto node:c)
    {
        printf("%d ",node);
    }
    printf("\n");*/
	if(c.size()==1)return c[0];
    sort(c.begin(),c.end());
    if(s>c[0])
    {
        for(int i=1;i<c.size()-1;i++)
        {
            if(t>=c[i]&&t<c[i+1])
            {
                return c[i];
            }
        }
        if(t>=c[c.size()-1]&&t<s)return c[c.size()-1];
        return c[0];
    }else
    {
        if(t<c[0]&&t>s)return c[0];
        for(int i=1;i<c.size()-1;i++)
        {
            if(t>c[i-1]&&t<c[i])
            {
                return c[i];
            }
        }
        return c[c.size()-1];
    }
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int i=1;i<c.size()-1;i++)
      |                     ~^~~~~~~~~~~
stations.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int i=1;i<c.size()-1;i++)
      |                     ~^~~~~~~~~~~

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