Submission #872192

#	Time	Username	Problem	Language	Result	Execution time	Memory
872192		kitkat12	Stations (IOI20_stations)	C++14	10 / 100	536 ms	1096 KiB

stations

#include <bits/stdc++.h>
#include <typeinfo>
#include "stations.h"
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
//#define all(v) v.begin(), v.end()
#define LPRINT(a, b) for (auto&(a) : (b))
#define li(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define lij(i,a,b) for (int (i) = (a); (i) <= (b); (i)++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))

//#define mod 1000000007
#define mod 998244353

vector<int> adj[1001];
bool visited[1001];
int timer = 0;
int m = 1000;
int dtime[1001], ftime[1001];

void dfs(int start){

	visited[start] = 1;
	dtime[start] = timer++;

	for(int neigh : adj[start]){
		if(!visited[neigh]){
			dfs(neigh);
		}
	}

	ftime[start] = timer++; 
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
	vector<int> labels(n,0);
	for(int i=0;i<n;i++){
		adj[i].clear();	
		visited[i] = 0;
	} 

	for(int i = 0; i<u.size(); i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	timer = 0;

	dfs(0);

	for(int i = 0; i<n; i++){
		labels[i] = m * dtime[i] + ftime[i];
	}

	return labels;
}

int find_next_station(int s, int t, vector<int> c)
{
	int l1 = s/m, r1 = s%m;
	int l2 = t/m, r2 = t%m;

	int ml = min(l1, l2);
	int mr = max(r1,r2);

	if(l1 <= l2 && r1 >= r2){
		for(int i = 0; i<c.size(); i++){
			int cd = c[i]/m, cf = c[i]%m;
			if( cd>=ml && cd<=(l1+l2-ml) && cf <= mr && cf >= (r1 + r2-mr) ){
				return c[i];
			}
		}
	}
	return c[0];
}

// int main()
// {
// 	ios_base::sync_with_stdio(false); cin.tie(NULL);

// 	return 0;
// }

Compilation message (stderr)

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

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