Submission #305428

#	Time	Username	Problem	Language	Result	Execution time	Memory
305428		ivan24	Stations (IOI20_stations)	C++14	52.32 / 100	1113 ms	1280 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

class Solver{
private:
    ll k,n,ctr;
    vvi adjList;
    vi dfs_num, sz, label;
    void DFS(ll v){
        dfs_num[v] = ctr++;
        for (auto u: adjList[v]){
            if (dfs_num[u] == -1){
                DFS(u);
                sz[v] += sz[u];
            }
        }
        label[v] = dfs_num[v]*1000+sz[v];
    }
public:
    Solver(ll k, ll n, vi u, vi v): k(k), n(n), adjList(n), dfs_num(n,-1), sz(n,1), label(n){
        //cout << "hello\n";
        for (ll i = 0; n-1 > i; i++){
            adjList[u[i]].push_back(v[i]);
            adjList[v[i]].push_back(u[i]);
        }
        //cout << "jello\n";
        ctr = 0;
        DFS(0);
    }
    vi get_labels(){
        return label;
    }
};

vi label(int n, int k, vi u, vi v) {
    //cout << n << " " << k << endl;
	Solver mySolver(k,n,u,v);
	return mySolver.get_labels();
}

int find_next_station(int s, int t, std::vector<int> c) {
	ii v = ii(s/1000,s%1000);
	ii e = ii(t/1000,t%1000);
	vii children(c.size());
	for (ll i = 0; c.size() > i; i++){
        children[i] = ii(c[i]/1000,c[i]%1000);
	}
	sort(children.begin(),children.end());
	for (ll i = 1; children.size() > i; i++){
        if (children[i].F+children[i].S > e.F && e.F >= children[i].F){
            return children[i].F*1000+children[i].S;
        }
	}
	return children[0].F*1000+children[0].S;
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:55:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   55 |  for (ll i = 0; c.size() > i; i++){
      |                 ~~~~~~~~~^~~
stations.cpp:59:33: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   59 |  for (ll i = 1; children.size() > i; i++){
      |                 ~~~~~~~~~~~~~~~~^~~
stations.cpp:52:5: warning: variable 'v' set but not used [-Wunused-but-set-variable]
   52 |  ii v = ii(s/1000,s%1000);
      |     ^

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