Submission #733948

#TimeUsernameProblemLanguageResultExecution timeMemory
733948vjudge1City Mapping (NOI18_citymapping)C++17
0 / 100
2 ms468 KiB
#include "citymapping.h" #include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define in insert #define all(x) x.begin(),x.end() #define pb push_back #define eb emplace_back #define ff first #define ss second // #define int long long typedef long long ll; typedef vector<int> vi; typedef set<int> si; typedef multiset<int> msi; typedef pair<int, int> pii; typedef vector<pii> vpii; template<typename T, typename U> ostream & operator << (ostream &out, const pair<T, U> &c) { out << c.first << ' ' << c.second; return out; } template<typename T> ostream & operator << (ostream &out, vector<T> &v) { const int sz = v.size(); for (int i = 0; i < sz; i++) { if (i) out << ' '; out << v[i]; } return out; } template<typename T> istream & operator >> (istream &in, vector<T> &v) { for (T &x : v) in >> x; return in; } template<typename T> void mxx(T &a, T b){if(b > a) a = b;} template<typename T> void mnn(T &a, T b){if(b < a) a = b;} void find_roads(int n, int Q, int A[], int B[], int W[]) { queue<pair<int, vector<int>>> q; vector<ll> dis(n + 1, 0); vector<int> tmp; int sum = 0; auto get = [&](int x, int y) -> ll { sum++; return get_distance(x, y); }; for(int i = 2; i <= n; i++) { dis[i] = get(1, i); tmp.pb(i); } q.push({1, tmp}); int cnt = 0; auto add = [&](int a, int b, int w) -> void { A[cnt] = a; B[cnt] = b; W[cnt++] = w; }; while(q.size()) { int x = q.front().ff; tmp = q.front().ss; q.pop(); sort(all(tmp), [&](int xx, int yy) -> bool { return dis[xx] < dis[yy]; }); vector<pair<int, vector<int>>> c; for(int y : tmp) { if(c.size() == 0) {c.pb({y, vector<int>()}); add(x, y, dis[y] - dis[x]);} else { bool did = 0; for(auto &it : c) { if(dis[y] - dis[x] * 2 - (dis[it.ff] - dis[x]) * 2 == dis[y] - dis[it.ff]) { it.ss.pb(y); did = 1; break; } } if(!did) { ll mn = dis[y] - dis[x]; add(x, y, mn); c.pb({y, vector<int>()}); } } } while(c.size()) { q.push(c.back()); c.pop_back(); } } // assert(cnt == n - 1); return; }
#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...