oj.uz

답안 #806971

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
806971 2023-08-04T11:44:01 Z hoangnghiep 공장들 (JOI14_factories) C++14
컴파일 오류
 0 ms 0 KB 
#include<bits/stdc++.h>
#include "factories.h"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define f first
#define s second
#define pii pair<ll,ll>
#define piii pair<ll,pair<ll,ll>>
#define vii vector<vector<ll>>
#define vi vector<ll>
#define cd complex<double>
#define endl '\n'
//#define multipletest
using namespace std;
const ll LIM=5000;
const ll INF = 1e18;
const string name="template";
ll n,m;
vector<pii> adj[LIM+5],adj_vt[LIM+5];
ll time_dfs=0;
pii euler_tour[1000005],sparse_table[20][LIM+5];
ll dist[LIM+5];
ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[0][LIM+5];
vector<ll> List;

priority_queue<pii,vector<pii>,greater<pii>> pq;

void dfs(ll u,ll parent,ll depth){
	h[u] = depth;
	
	tin[u] = time_dfs;
	
	euler_tour[time_dfs++] = {depth,u};
	
	low[0][u] = parent;
	 
	for(auto v:adj[u]){
		if(v.f!=parent){
			dfs(v.f,u,depth + 1);
		}
		
		euler_tour[time_dfs++] = {depth,u};
		
		up_weight[0][u] = v.s;	
	}
	tout[u] = time_dfs;
}

ll lca(ll u,ll v){
	if(tin[u]>tin[v]){
		swap(tin[u],tin[v]);
	}
	ll bt = 63 - __builtin_clzll(tin[v]-tin[u]+1);
	pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]);
	return mn.s;
}

ll lift_weight(ll u,ll k){
	ll tmp=0;
	ll w = 0;
	while(k>0){
		if(k%2==1){
			w+=up_weight[tmp][u];
			u=low[u][tmp];
		}
		k>>=1;
		tmp++;
	}
	return w;
}

bool cmp(ll a,ll b){
	return tin[a]<tin[b];
}

ll isSubtree(ll u,ll v)
{
	return tin[u]<=tin[v] && tin[v]<=tout[u];
}

void Init(int N, int A[], int B[], int D[]){
	n=N;
	time_dfs=0;
	for(ll i=1;i<=n;++i){
		adj[i].clear();
		adj_vt[i].clear();
	}
	for(ll i=0;i<n-1;++i){
		A[i]++;
		B[i]++;
	    adj[A[i]].push_back({B[i],D[i]});
	    adj[B[i]].push_back({A[i],D[i]});
	}
	for(ll i=1;i<=n;++i){
		dist[i]=-1;
	}
	dfs(1,0,0);
	
	for(ll i=0;i<time_dfs;++i){
		sparse_table[0][i]  = euler_tour[i];
	}
	
	for(ll i=0;i<20;++i){
		for(ll j=0;j+(1<<i)-1<time_dfs;++j){
			sparse_table[i][j] = min(sparse_table[i-1][j],sparse_table[i-1][j + (1<<(i-1))]);
		}
	}
	
	for(ll i=1;i<20;++i){
		for(ll j=1;j<=n;++j){
			low[i][j] = low[i-1][low[i-1][j]];
			up_weight[i][j] = up_weight[i-1][j] + up_weight[i-1][low[i-1][j]];
		}
	}
	
}

ll Query(ll S, int X[], int T, int Y[]){
    for(ll i=0;i<S;++i){
    	List.push_back(++X[i]);
	}
	
	for(ll i=0;i<T;++i){
		List.push_back(++Y[i]);
	} 
	 
	sort(List.begin(),List.end(),cmp);
	
	for(ll i=1;i<S+T;++i){
		List.push_back(lca(List[i],List[i-1]));
	}
	
	sort(List.begin(),List.end(),cmp);
	
	List.erase(unique(List.begin(),List.end()),List.end());
	vector<ll> st;
	for(ll i=0;i<List.size();++i){
		ll u = List[i];
		while(st.size()>=2 && !isSubtree(st.back(),u)){
			ll x = st[st.size()-2];
			ll y= st.back();
			ll LCA = lca(x,y);
			ll w=lift_weight(x,h[x] - h[LCA]) + lift_weight(y,h[y] - h[LCA]);
			adj_vt[x].push_back({y,w});
			adj_vt[y].push_back({x,w});
			st.pop_back();
		}
		st.push_back(u);
	}
	while(st.size()>=2){
			ll x = st[st.size()-2];
			ll y= st.back();
			ll LCA = lca(x,y);
			ll w=lift_weight(x,h[x] - h[LCA]) + lift_weight(y,h[y] - h[LCA]);
			adj_vt[x].push_back({y,w});
			adj_vt[y].push_back({x,w});
			st.pop_back();
	}
	for(ll i=0;i<T;++i){
		pq.push({0,Y[i]});
	}
	while(!pq.empty()){
		ll u = pq.top().s;
		ll w= pq.top().f;
		if(dist[u]!=-1) continue;
		dist[u] = w;
		for(auto v:adj_vt[u]){
			pq.push({w + v.s,v.f});
		}
	}
	ll ans=INF;
	for(ll i=0;i<S;++i){
		ans = min(ans,dist[X[i]]);
	}
	return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(long long int, int*, int, int*)':
factories.cpp:138:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for(ll i=0;i<List.size();++i){
      |             ~^~~~~~~~~~~~
factories.cpp: In function 'void dfs(long long int, long long int, long long int)':
factories.cpp:36:7: warning: array subscript 0 is outside array bounds of 'long long int [0][5005]' [-Warray-bounds]
   36 |  low[0][u] = parent;
      |  ~~~~~^
factories.cpp:24:57: note: while referencing 'low'
   24 | ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[0][LIM+5];
      |                                                         ^~~
factories.cpp: In function 'long long int lift_weight(long long int, long long int)':
factories.cpp:65:11: warning: array subscript u is outside array bounds of 'long long int [0][5005]' [-Warray-bounds]
   65 |    u=low[u][tmp];
      |      ~~~~~^
factories.cpp:24:57: note: while referencing 'low'
   24 | ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[0][LIM+5];
      |                                                         ^~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:112:32: warning: array subscript <unknown> is outside array bounds of 'long long int [0][5005]' [-Warray-bounds]
  112 |    low[i][j] = low[i-1][low[i-1][j]];
      |                         ~~~~~~~^
factories.cpp:24:57: note: while referencing 'low'
   24 | ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[0][LIM+5];
      |                                                         ^~~
factories.cpp:112:23: warning: array subscript <unknown> is outside array bounds of 'long long int [0][5005]' [-Warray-bounds]
  112 |    low[i][j] = low[i-1][low[i-1][j]];
      |                ~~~~~~~^
factories.cpp:24:57: note: while referencing 'low'
   24 | ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[0][LIM+5];
      |                                                         ^~~
factories.cpp:112:9: warning: array subscript i is outside array bounds of 'long long int [0][5005]' [-Warray-bounds]
  112 |    low[i][j] = low[i-1][low[i-1][j]];
      |    ~~~~~^
factories.cpp:24:57: note: while referencing 'low'
   24 | ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[0][LIM+5];
      |                                                         ^~~
factories.cpp: In function 'long long int Query(long long int, int*, int, int*)':
factories.cpp:65:11: warning: array subscript u is outside array bounds of 'long long int [0][5005]' [-Warray-bounds]
   65 |    u=low[u][tmp];
      |      ~~~~~^
factories.cpp:24:57: note: while referencing 'low'
   24 | ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[0][LIM+5];
      |                                                         ^~~
factories.cpp:65:11: warning: array subscript u is outside array bounds of 'long long int [0][5005]' [-Warray-bounds]
   65 |    u=low[u][tmp];
      |      ~~~~~^
factories.cpp:24:57: note: while referencing 'low'
   24 | ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[0][LIM+5];
      |                                                         ^~~
factories.cpp:65:11: warning: array subscript u is outside array bounds of 'long long int [0][5005]' [-Warray-bounds]
   65 |    u=low[u][tmp];
      |      ~~~~~^
factories.cpp:24:57: note: while referencing 'low'
   24 | ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[0][LIM+5];
      |                                                         ^~~
factories.cpp:65:11: warning: array subscript u is outside array bounds of 'long long int [0][5005]' [-Warray-bounds]
   65 |    u=low[u][tmp];
      |      ~~~~~^
factories.cpp:24:57: note: while referencing 'low'
   24 | ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[0][LIM+5];
      |                                                         ^~~
/usr/bin/ld: /tmp/cccgLxb4.o: in function `main':
grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status