제출 #743547

#제출 시각아이디문제언어결과실행 시간메모리
743547Valters07공장들 (JOI14_factories)C++14
15 / 100
8053 ms121104 KiB
#include "factories.h" #include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0); #define en cin.close();return 0; #define ll long long #define pb push_back #define fi first #define se second using namespace std; const int N = 5e5+5; const int LOG = log2(N)+2; vector<pair<int,int> > g[N]; vector<pair<int,ll> > g2[N]; int par[N][LOG]; int tin[N], tout[N], tt; int col[N]; ll dist[N], mindist; void dfs(int u, int p) { tin[u]=++tt; par[u][0]=p; for(int i = 1;i<LOG;i++) par[u][i]=par[par[u][i-1]][i-1]; for(auto v:g[u]) if(v.fi!=p) dist[v.fi]=dist[u]+v.se, dfs(v.fi,u); tout[u]=tt; } bool isanc(int u, int v) { return (tin[u]<=tin[v]&&tout[v]<=tout[u]); } int lca(int u, int v) { if(isanc(u,v)) return u; if(isanc(v,u)) return v; for(int i = LOG-1;i>=0;i--) if(!isanc(par[u][i],v)) u=par[u][i]; return par[u][0]; } void Init(int n, int a[], int b[], int d[]) { for(int i = 0;i<n-1;i++) g[a[i]].pb({b[i],d[i]}), g[b[i]].pb({a[i],d[i]}); dfs(0,0); } void con(int u, int v) { if(u==v) return; ll d = abs(dist[u]-dist[v]); g2[u].pb({v,d}); g2[v].pb({u,d}); } int createvt(vector<int> &nodes) { sort(nodes.begin(),nodes.end(),[](int &i, int &j){return (tin[i]<tin[j]);}); for(int i = (int)(nodes.size())-2;i>=0;i--) nodes.pb(lca(nodes[i],nodes[i+1])); sort(nodes.begin(),nodes.end(),[](int &i, int &j){return (tin[i]<tin[j]);}); vector<int> ve; ve.pb(nodes[0]); for(int i = 1;i<nodes.size();i++) { while(!isanc(ve.back(),nodes[i])) con(ve.back(),ve[ve.size()-2]), ve.pop_back(); ve.pb(nodes[i]); } while(ve.size()>1) con(ve.back(),ve[ve.size()-2]), ve.pop_back(); return ve[0]; } pair<ll,ll> dfs2(int u, int p) { ll min1 = 1e18, min2 = 1e18; if(col[u]==1) min1=0; else if(col[u]==2) min2=0; for(auto v:g[u]) { if(v.fi!=p) { pair<ll,ll> t = dfs2(v.fi,u); min1=min(min1,t.fi+v.se); min2=min(min2,t.se+v.se); } } mindist=min(mindist,min1+min2); return {min1,min2}; } long long Query(int n, int x[], int m, int y[]) { vector<int> nodes; for(int i = 0;i<n;i++) nodes.pb(x[i]), col[x[i]]=1; for(int i = 0;i<m;i++) nodes.pb(y[i]), col[y[i]]=2; int r = createvt(nodes); mindist = 1e18; dfs2(r,r); for(auto x:nodes) g2[x].clear(), col[x]=0; return mindist; }

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'int createvt(std::vector<int>&)':
factories.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 1;i<nodes.size();i++)
      |                   ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...