Submission #1292758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292758		lucasdmy	Stations (IOI20_stations)	C++20	0 / 100	4 ms	588 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1010;
vector<int>graph[MAXN], ord, aux(MAXN), sub_size(MAXN), inv(MAXN), labels;
void dfs(int x, int p){
    ord.push_back(x);
    aux[x]=0;
    for(int k=0;k<graph[x].size();k++){
        int neighbour=graph[x][k];
        if(neighbour!=p){
            dfs(neighbour, x);
            aux[x]+=1+aux[neighbour];
        }
    }
}
vector<int> label(int n, int m, vector<int>a, vector<int>b){
    for(int k=0;k<n;k++){
        graph[k].clear();
    }
    ord.clear();
    for(int k=0;k<n-1;k++){
        graph[a[k]].push_back(b[k]);
        graph[b[k]].push_back(a[k]);
    }
    dfs(0, 0);
    labels.resize(n);
    for(int k=0;k<n;k++){
        labels[ord[k]]=k;
        inv[k]=ord[k];
        sub_size[k]=aux[ord[k]];
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<graph[k].size();i++){
            graph[k][i]=labels[graph[k][i]];
        }
        sort(graph[k].begin(), graph[k].end());
    }
    return labels;
} 
int find_next_station(int at, int end, vector<int>adj){
    if(end>at+sub_size[at] or end<at){
        return graph[inv[at]][0];
    }
    for(int k=graph[inv[at]].size()-1;k>0;k--){
        if(end>=graph[inv[at]][k]){
            return graph[inv[at]][k];
        }
    }
    return 0;
}
/*int main(){
    int r;
    cin>>r;
    while(r--){
        int n, m;
        cin>>n>>m;
        vector<int>a(n-1), b(n-1);
        for(int k=0;k<n-1;k++){
            cin>>a[k];
        }
        for(int k=0;k<n-1;k++){
            cin>>b[k];
        }
        label(n, m, a, b);
        int q;
        cin>>q;
        int at, end;
        for(int k=0;k<q;k++){
            cin>>at>>end;
            vector<int>adj;
            for(int i=0;i<graph[at].size();i++){
                adj.push_back(graph[at][i]);
            }
            sort(adj.begin(), adj.end());
            cout<<find_next_station(at, end, adj)<<endl<<endl;
        }
    }
}*/

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