Submission #1292855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292855		lucasdmy	Stations (IOI20_stations)	C++20	5 / 100	397 ms	584 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1010;
vector<int>graph[MAXN], labels, sub_size(MAXN), inv(MAXN);
int c=0;
void dfs(int x, int p){
    labels[x]=c;
    inv[c]=x;
    c++;
    sub_size[x]=0;
    for(int k=0;k<graph[x].size();k++){
        if(graph[x][k]!=p){
            dfs(graph[x][k], x);
            sub_size[x]+=1+sub_size[graph[x][k]];
        }
    }
}
vector<int>label(int n, int m, vector<int>a, vector<int>b){
    for(int k=0;k<n;k++){
        graph[k].clear();
    }
    labels.resize(n);
    vector<int>deg(n, 0);
    for(int k=0;k<n-1;k++){
        graph[a[k]].push_back(b[k]);
        graph[b[k]].push_back(a[k]);
        deg[a[k]]++;
        deg[b[k]]++;
    }
    c=0;
    for(int k=0;k<n;k++){
        if(deg[k]==1){
            dfs(k, -1);
            break;
        }
    }
    return labels;
}
int find_next_station(int at, int end, vector<int>adj){
    if(adj.size()==1){
        return adj[0];
    }else if(end<at){
        return adj[0];
    }else{
        return adj[1];
    }
}

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