Submission #712410

#TimeUsernameProblemLanguageResultExecution timeMemory
712410AntekbConstruction of Highway (JOI18_construction)C++17
0 / 100
7 ms9556 KiB
#include<bits/stdc++.h> #define st first #define nd second #define pb push_back #define eb emplace_back #define mp make_pair #define pp pop_back #define all(x) (x).begin(), (x).end() using namespace std; void debug(){cerr<<"\n";} template<typename H, typename... T> void debug(H h, T... t){ cerr<<h; if(sizeof...(t))cerr<<", "; debug(t...); } #define deb(x...) cerr<<#x<<" = ";debug(x); using ll = long long; using pii = pair<int, int>; using vi = vector<int>; using vii = vector<pii>; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const int N=1<<17; vi E[N]; int pre[N], sz[N], par[N], sci[N], dep[N], val[N], co[N]; int wsk; void dfs_sz(int v){ for(int u:E[v]){ if(u!=par[v]){ par[u]=v; dep[u]=dep[v]+1; dfs_sz(u); sz[v]+=sz[u]; } } sz[v]+=1; for(int &u:E[v])if(u==par[v])swap(u, E[v].back()); if(v!=1)E[v].pp(); for(int &u:E[v])if(sz[u]>sz[E[v][0]])swap(u, E[v][0]); //deb(v, E[v].size()); } void dfs(int v){ co[wsk]=v; pre[v]=wsk++; for(int u:E[v]){ //deb(v, u); if(u==E[v][0])sci[wsk]=sci[pre[v]]; else{ sci[wsk]=wsk; //deb(v, wsk); } dfs(u); } } set<int> S[N]; int sum[N+N]; int add(int v, int c){ int ans=0; for(v+=N; v; v>>=1){ sum[v]+=c; if(!(v&1)){ ans+=sum[v+1]; } } return ans; } ll calc(int v){ vector<pair<int, int> > V; v=pre[v]; int t=val[v]; bool czy=1; while(true){ int u=sci[v]; //deb(v, u, S[u].size()); if(S[u].size()){ //deb(*S[u].begin()); } vector<pair<int, int> > V2; int prv=u-1; while(prv<v-czy){ //deb("a"); //assert(S[u].size()); int a=*S[u].begin(); if(a>v-czy){ V2.eb(v-czy-prv, val[a]); } else{ V2.eb(a-prv, val[a]); S[u].erase(a); } prv=a; } reverse(all(V2)); for(pii &i:V2)V.pb(i); S[u].insert(v); val[v]=t; if(u==0)break; v=pre[par[co[u]]]; czy=0; } reverse(all(V)); //deb(V.size()); for(pii i:V){ //deb(i.st, i.nd); } ll ans=0; for(int i=0; i<V.size(); i++){ ans+=add(V[i].nd, V[i].st); } for(int i=0; i<V.size(); i++){ add(V[i].nd, -V[i].st); } return ans; } int main(){ //ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; map<int, int> M; vi V(n); for(int &i:V)cin>>i, M[i]=1; int wsk2=1; for(auto &i:M){ i.nd=wsk2++; } vector<pii> edg(n-1); for(pii &i:edg)cin>>i.st>>i.nd, E[i.st].pb(i.nd), E[i.nd].pb(i.st); dfs_sz(1); dfs(1); for(int i=1; i<=n; i++){ //deb(i, pre[i], par[i], val[i], sci[pre[i]], sz[i]); } S[0].insert(0); for(int i=1; i<=n; i++){ val[pre[i]]=M[V[i-1]]; } for(pii i:edg){ cout<<calc(i.nd)<<"\n"; } }

Compilation message (stderr)

construction.cpp: In function 'll calc(int)':
construction.cpp:108:10: warning: variable 'i' set but not used [-Wunused-but-set-variable]
  108 |  for(pii i:V){
      |          ^
construction.cpp:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
construction.cpp:115:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...