Submission #828407

#	Time	Username	Problem	Language	Result	Execution time	Memory
828407		minhcool	Stations (IOI20_stations)	C++17	0 / 100	656 ms	24196 KiB

stations

#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#include <vector>
 
#define pb push_back
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 5e5 + 5, oo = 1e18 + 7;
 
int n;
vector<int> Adj[N];
 
int l[N], r[N], d[N];
 
vector<int> vis;
 
void dfs(int u, int p){
	vis.pb(u);
	l[u] = vis.size();
	for(auto v : Adj[u]){
		if(v == p) continue;
		dfs(v, u);
		vis.pb(u);
	}
	vis.pb(u);
	r[u] = vis.size();
}
 
//vector<int> vis;
 
int tol[1005][1005];
ii tol2[600005];
 
/*
void prep(){
	int cnt = 0;
	for(int i = 1; i <= 1000; i++){
		for(int j = i; j <= 1000; j++){
			tol[i][j] = cnt;
			tol2[cnt] = {i, j};
			cnt++;
		}
	}
}*/
 
vector<int> label(int n_, int k, vector<int> u, vector<int> v) {
	n = n_;
	vis.clear();
	for(int i = 0; i < n; i++) Adj[i].clear();
	for(int i = 0; i < (n - 1); i++){
		Adj[u[i]].pb(v[i]); Adj[v[i]].pb(u[i]);
	}
	dfs(0, 0);
	vector<int> labels(n);
	for(int i = 0; i < n; i++){
		//cout << l[i] << " " << r[i] << " " << tol[l[i]][r[i]] << "\n";
		//labels[i] = tol[l[i]][r[i]];
		if(!d[i]) labels[i] = l[i];
		else labels[i] = r[i];
	}
	return labels;
	/*
	std::vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[i] = i;
	}
	return labels;*/
}

/*
bool anc(int lab1, int lab2){
	ii temp1 = {lab1 / 1000 + 1, lab1 % 1000 + 1}, temp2 = {lab2 / 1000 + 1, lab2 % 1000 + 1};
	return (temp1.fi <= temp2.fi && temp1.se >= temp2.se);
}*/
 
int find_next_station(int s, int t, vector<int> c) {
	//cout << c.size() << "\n";
	//return 0;
	int mini = oo;
	for(auto it : c) mini = min(mini, it);
	if(mini < s){// which means that s is right
		for(int i = 1; i < c.size(); i++){
			int le = c[i], ri;
			if(i != c.size() - 1) ri = c[i + 1] - 1;
			else ri = s;
			if(le >= t && ri <= t) return c[i];
		}
		return c[0];
	}
	else{
		for(int i = 0; (i + 1) < c.size(); i++){
			int le = (i ? c[i - 1] + 1 : s + 1), ri = c[i];
			if(le >= t && ri <= t) return c[i];
		}
		return c.back();
	}
	/*
	pair<int, int> mini = {oo, oo}, maxi = {-1, -1};
	for(int i = 0; i < c.size(); i++){
		ii tempo = {c[i] / 1000 + 1, c[i] % 1000 + 1};
		maxi = max(maxi, {tempo.se - tempo.fi + 1, c[i]});
		if(anc(c[i], t)){
			mini = min(mini, {tempo.se - tempo.fi + 1, c[i]});
		}
	}
	if(mini.se != oo) return mini.se;
	else return maxi.se;
	if(anc(c[1], t)) return c[1];
    else if(anc(c[2], t)) return c[2];
    else return c[0];*/
	//return c[0];
}

Compilation message (stderr)

stations.cpp:15:34: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int N = 5e5 + 5, oo = 1e18 + 7;
      |                             ~~~~~^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for(int i = 1; i < c.size(); i++){
      |                  ~~^~~~~~~~~~
stations.cpp:91:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    if(i != c.size() - 1) ri = c[i + 1] - 1;
      |       ~~^~~~~~~~~~~~~~~
stations.cpp:98:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int i = 0; (i + 1) < c.size(); i++){
      |                  ~~~~~~~~^~~~~~~~~~

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