Submission #1311281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311281		ayathk	Stations (IOI20_stations)	C++20	0 / 100	390 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> dp(n,100000);
    vector <vector <int>> adj(n);
    int b = -1;
    for(int i = 0;i < n - 1;i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
        if(adj[u[i]].size() > 2)b = u[i];
        else if(adj[v[i]].size() > 2)b = v[i];
    }
    dp[0] = 1;
    int cnt = 1;
    queue <int> t;
    for(int i : adj[b]){
        dp[i] *= cnt;
        dp[i]++;
        t.push(i);
    }
    while(!t.empty()){
        int f = t.front();
        t.pop();

        for(int i : adj[f]){
            if(dp[i] != 100000)continue;
            dp[i] = dp[f] + 1;
        }
    }

    return dp;
}

int find_next_station(int s, int t, vector<int> c) {
    if(s == 100000){
        for(int i : c){
            if(i/100000 == t/100000)return i;
        }
    }

    if(t/100000 == s/100000){
        if(t > s){
            return s + 1;
        }
        else{
            return s - 1;
        }
    }
    else{
        if(s % 10 == 1){
            return 1;
        }
        else{
            return s - 1;
        }
    }
}

/*signed main(){
    vector <int> a = label(5, 8 ,{0,0,1,1}, {1,2,4,3});
    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