Submission #1303760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303760		opeleklanos	Stations (IOI20_stations)	C++20	10 / 100	404 ms	576 KiB

stations

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include "stations.h"
using namespace std;

vector<vector<int>> adj;
vector<int> lb;
vector<int> indx;
int t = 0;

void dfs(int st){
    if(indx[st] != -1) return;
    indx[st] = t;
    lb[st] = t*1000;
    t++;
    for(auto i : adj[st]) dfs(i);
    lb[st] += t-1;
}

vector<int> label (int n, int k, vector<int> u, vector<int> v){
    adj.assign(n, {});
    for(int i = 0; i<n-1; i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    lb.assign(n, -1);
    indx.assign(n, -1);
    dfs(0);
    return lb;
}

int subtree(int par, int u){
    return (((par/1000) <= (u/1000)) && ((u%1000) <= (par%1000)));
}


int find_next_station(int s, int t, vector<int> c){
    int par = 0;
    for(auto i : c){
        if(subtree(i, t) && !subtree(i, s)) return i;
        else if(subtree(i, s)) par = i;
    }
    return par;
}


// int main(void){
//     freopen("input.txt", "r", stdin);
//     int n; cin>>n;
//     vector<int> u(n-1, 0);
//     vector<int> v(n-1, 0);
//     for(int i = 0; i<n-1; i++) cin>>u[i]>>v[i];
//     label(n, 100000000, u, v);
//     cout<<find_next_station(3, 6);
    
// }

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