Submission #607353

#	Time	Username	Problem	Language	Result	Execution time	Memory
607353		gagik_2007	Stations (IOI20_stations)	C++17	100 / 100	915 ms	844 KiB

stations

#include "stations.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll itn;

#define ff first
#define ss second

ll n;
vector<int>g[1007];
int tin[1507], tout[1507];
int timer = 0;
vector<int>d;

void dfs(int v, int par = -1) {
	tin[v] = timer++;
	for (int i = 0; i < g[v].size(); i++) {
		int to = g[v][i];
		if (to != par) {
			dfs(to, v);
		}
	}
	tout[v] = timer++;
}

void raspr(int v, int par=-1, bool is_tin=true){
    if(is_tin){
        d.push_back(v);
    }
    for (int i = 0; i < g[v].size(); i++) {
		int to = g[v][i];
		if (to != par) {
			raspr(to, v, !is_tin);
		}
	}
	if(!is_tin){
        d.push_back(v);
	}
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> lbl(n);
	for (int i = 0; i < n - 1; i++) {
		g[v[i]].push_back(u[i]);
		g[u[i]].push_back(v[i]);
	}
	for(int i=0;i<n;i++){
        sort(g[i].begin(),g[i].end());
	}
	raspr(0);
	int tmr=0;
	for(auto x:d){
        lbl[x]=tmr++;
	}
	for (int i = 0; i < n; i++) {
		tin[i] = 0;
		tout[i] = 0;
		timer = 0;
		g[i].clear();
	}
	d.clear();
	return lbl;
}

bool papa(int iv, int ov, int u) {
	return (iv <= u && ov >= u);
}

bool is_in(int s, vector<int> c){
    int mn=1e9;
    for(auto x:c){
        mn=min(mn,x);
    }
    return mn>=s;
}

int find_next_station(int s, int t, vector<int> c) {
	if (c.size() == 1)return c[0];
	sort(c.begin(),c.end());
	if(s==0){
        for(int i=0;i<c.size();i++){
            if(t<=c[i]){
                //cout<<c[i]<<" 1"<<endl;
                return c[i];
            }
        }
        //cout<<c[0]<<" 1"<<endl;
        return c[0];
	}
	if(is_in(s,c)){
        int is=s;
        int par=c[c.size()-1];
        int os=c[c.size()-2];
        if(!papa(is,os,t)){
            return par;
        }
        for(int i=0;i<c.size();i++){
            if(t<=c[i]){
                //cout<<c[i]<<" 1"<<endl;
                return c[i];
            }
        }
        //cout<<c[0]<<" 1"<<endl;
        return c[0];
	}
	else{
        int os=s;
        int par=c[0];
        //cout<<"par: "<<par<<endl;
        int is=c[1]-1;
        if(!papa(is,os,t)){
            return par;
        }
        for(int i=c.size()-1;i>=0;i--){
            //cout<<"ditarkel: "<<c[i]<<endl;
            if(t>=c[i]){
                //cout<<c[i]<<" 2"<<endl;
                return c[i];
            }
        }
        //cout<<c[c.size()-1]<<" 2"<<endl;
        return c[c.size()-1];
	}
}

/*
1
8 1000000
0 1
0 2
1 3
1 4
3 5
3 6
5 7
5
7 2 5
2 3 0
6 5 3
7 4 5
6 4 3
1 8 1000 0 1 0 2 1 3 1 4 3 5 3 6 5 7 5 7 2 5 2 3 0 6 5 3 7 4 5 6 4 3
1 8 1000000
0 1
0 2
1 3
1 4
2 5
2 6
3 7
5
7 2 3
1 7 3
2 5 5
0 5 2
5 0 2

1
6 1000
0 1
0 2
0 3
3 4
3 5
5
0 1 1
0 2 2
0 3 3
0 4 3
0 5 3
*/

Compilation message (stderr)

stations.cpp: In function 'void dfs(int, int)':
stations.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0; i < g[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
stations.cpp: In function 'void raspr(int, int, bool)':
stations.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < g[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int i=0;i<c.size();i++){
      |                     ~^~~~~~~~~
stations.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for(int i=0;i<c.size();i++){
      |                     ~^~~~~~~~~

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