Submission #1192371

#TimeUsernameProblemLanguageResultExecution timeMemory
1192371woodCity Mapping (NOI18_citymapping)C++20
13 / 100
14 ms8392 KiB
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define eb emplace_back #define fi first #define se second typedef long long ll; typedef pair<int, int> pint; typedef pair<ll, ll> pll; #define vint vector<int> #define vpint vector<pint> #define vll vector<ll> #define vpll vector<pll> #define fast_cin() \ ios_base::sync_with_stdio(false); \ cin.tie(NULL); \ cout.tie(NULL) #define MOD %= 1000000007 #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // are you certain that you have a clear idea of your code in your head? // don't rush to the computer it'll only make it worse, it never works // if this is the first time reading this you definitely need to go back and // think about the implementation pint find_ends(int N, int Q){ int mx = 0; int e1 = 0; int e2 = 0; for(int i = 1; i<N; i++){ int k = get_distance(1,i+1); if(k>mx){ mx = k; e1 = i; } } for(int i = 0; i<N; i++){ if(i==e1) continue; int k = get_distance(e1+1,i+1); if (k>mx){ mx = k; e2 = i; } } return make_pair(e1,e2); } void find_roads(int N, int Q, int A[], int B[], int W[]) { int n = N; int cur = 0; int mx = 0; pint ends = find_ends(N,Q); cerr<<ends.fi<<' '<<ends.se; pint dist[n*n]; memset(dist,0,sizeof dist); for(int i = 0; i<n; i++){ if(i==ends.fi) dist[i] = make_pair(i,0); dist[i] = make_pair(get_distance(ends.fi+1,i+1),i); } for(int i = 0; i<n; i++) cerr<<dist[i].fi<<' '<<dist[i].se<<'\n'; cerr<<endl; sort(dist,dist+n); for(int i = 0; i<n-1;i++){ A[i] = dist[i].se+1; B[i] = dist[i+1].se+1; W[i] = dist[i+1].fi-dist[i].fi; } for(int i = 0; i<n-1; i++) cerr<<A[i]<<' '<<B[i]<<' '<<W[i]<<'\n';; cerr<<endl; 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...