Submission #1311177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311177		ayathk	Stations (IOI20_stations)	C++20	0 / 100	392 ms	488 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first 
#define se second
#define all(a) a.begin(), a.end()

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

    queue <int> t;
    for(int i = 0;i < n;i++){
        if(adj[i].size() == 1){
            t.push(i);
            break;
        }
    }

    int cnt = 0;
    vector <bool> vis(n,0);
    while(!t.empty()){
        int f = t.front();
        t.pop();
        vis[f] = 1;
        labels[f] = cnt;
        for(int i : adj[f]){
            if(vis[i])continue;
            t.push(i);
        }
        cnt++;
    }

	return labels;
}
string binary(int num){
    string an;
    while(num > 0){
        an += ('0' + num%2);
        num /= 2;
    }
    reverse(all(an));
    return an;
}
int find_next_station(int s, int t, vector<int> c) {
    if(c.size() == 1)return c[0];

    bool dw = 0;
    string ss = binary(s), tt = binary(t);
    for(int i = 0;i < min(ss.size(), tt.size());i++){
        if(ss[i] != tt[i]){
            dw = 1;
            break;
        }
    }
    if(!dw){
        return s/2;
    }

    if(tt[ss.size()] == 1){
        return s * 2 + 1;
    }
    return s*2;
}

/*signed main(){
    vector <int> a = label(5, 8 ,{4,1,2,3,0}, {0,4,0,2,2});
    for(int i : a){
        cout<<i<<' ';
    }
}*/

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