Submission #545185

#	Time	Username	Problem	Language	Result	Execution time	Memory
545185		PiejanVDC	Stations (IOI20_stations)	C++17	0 / 100	2017 ms	1400 KiB

stations

#include <bits/stdc++.h>
#include "stations.h"
 
using namespace std;
 
const int mxN = 1005;
 
map<pair<int,int>, bitset<mxN>>mp;
 
vector<int>adj[mxN];
 
bitset<mxN> dfs(int u, int e = -1) {
    bitset<mxN>b;
    for(auto z : adj[u]) if(z != e) {
        mp[{u,z}] |= dfs(z,u);
        mp[{u,z}][z] = 1;
        b |= mp[{u,z}];
    }
    return b;
}
 
void prep() {
    for(int i = 0 ; i < mxN ; i++)
	adj[i].clear();
    mp.clear();
}

vector<int>label(int n, int k, vector<int>u, vector<int>v) {
    prep();
    for(int i = 0 ; i < n-1 ; i++)
        adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
    vector<int>ret(n);
    for(int i = 0 ; i < n ; i++) {
        dfs(i);
        ret[i] = i;
    }
    return ret;
}
 
int find_next_station(int s, int t, vector<int>c) {
    for(auto z : c) {
        if(mp[{s,z}][t])
            return z;
    }
    assert(0);
}

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