Submission #1064870

#TimeUsernameProblemLanguageResultExecution timeMemory
1064870thatsgonzalezStations (IOI20_stations)C++14
0 / 100
356 ms16632 KiB
#include "stations.h" #include <vector> #include <bits/stdc++.h> using namespace std; #define s second #define f first vector<vector<int>> tree; vector<vector<int>> dist; int const inf = INT_MAX; std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { std::vector<int> labels(n); for (int i = 0; i < n; i++) { labels[i] = i; } tree.resize(n); dist.assign(n,vector<int>(n,inf)); for(int i = 0; i<n-1; i++){ tree[u[i]].push_back(v[i]); tree[v[i]].push_back(u[i]); } for(int i = 0; i<n; i++){ priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; dist[i][i] = 0; pq.push({0,i}); while(!pq.empty()){ int u = pq.top().s; int w = pq.top().f; pq.pop(); if(dist[i][u]!=w) continue; for(auto &x: tree[u]){ if(dist[i][x] > dist[i][u] + 1){ dist[i][x] = dist[i][u] + 1; pq.push({dist[i][x],x}); } } } } return labels; } int find_next_station(int s, int t, std::vector<int> c) { int mn = INT_MAX; int res = -1; for(auto &x: c){ if(dist[x][t]<mn){ mn = dist[x][t]; res = x; } } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...