Submission #606714

#	Time	Username	Problem	Language	Result	Execution time	Memory
606714		gagik_2007	Stations (IOI20_stations)	C++17	5 / 100	929 ms	664 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]);
	}
	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,mx=0;
    for(auto x:c){
        mx=max(mx,x);
        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){
        int is=s;
        int os=c[c.size()-1];
        for(int i=1;i<c.size();i++){
            if(papa(c[i-1]+1,c[i],t)){
                //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=1;i<c.size()-1;i++){
            if(papa(c[i-1],c[i],t)){
                //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];
        if(!papa(is,os,t)){
            return par;
        }
        for(int i=1;i<c.size()-1;i++){
            //cout<<"ditarkel: "<<c[i]<<endl;
            if(papa(c[i],c[i+1],t)){
                //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=1;i<c.size();i++){
      |                     ~^~~~~~~~~
stations.cpp:97:13: warning: unused variable 'is' [-Wunused-variable]
   97 |         int is=s;
      |             ^~
stations.cpp:98:13: warning: unused variable 'os' [-Wunused-variable]
   98 |         int os=c[c.size()-1];
      |             ^~
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=1;i<c.size()-1;i++){
      |                     ~^~~~~~~~~~~
stations.cpp:132:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for(int i=1;i<c.size()-1;i++){
      |                     ~^~~~~~~~~~~

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