Submission #553806

#	Time	Username	Problem	Language	Result	Execution time	Memory
553806		QwertyPi	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
const int N = 5e5 + 13;
const int inf = 1LL << 60;
int tail[N], d[N], p[N], dep[N];
vector<pii> G[N];
void dfs(int v, int par = -1){
	int out = 0, son = -1;
	for(auto i : G[v]){
		if(i.fi != par){
			d[i.fi] = d[v] + i.se;
			p[i.fi] = v;
			dfs(i.fi, v);
			out++; son = i.fi;
		}
	}
	tail[v] = v, p[tail[v]] = p[v]; if(v != 0) dep[tail[v]] = dep[p[v]] + 1;
	// tail[v] = (out == 1 ? tail[son] : v), p[tail[v]] = p[v], dep[tail[v]] = dep[];
}

void dfs2(int v, int par = -1){
	for(auto i : G[v]){
		if(i.fi != par){
			if(v == tail[v]) dep[tail[i.fi]] = dep[v] + 1;
			dfs2(i.fi, v);
		}
	}
}

struct state{
	int v, dis, colour;
	bool operator< (const state& o) const{
		return v < o.v;
	}
};

vector<state> qry[N];

void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N - 1; i++){
		int u, v, w;
		cin >> u >> v >> w;
		G[u].pb({v, w});
		G[v].pb({u, w});
	}
	dfs(0);
	dfs2(0);
}

long long Query(int S, int X[], int T, int Y[]) {
	for(int j = n - 1; j >= 0; j--) qry[j].clear();
	for(int j = 0; j < S; j++){
		int v = X[j];
		qry[dep[tail[v]]].pb({tail[v], d[v] - d[tail[v]], 0});
	}
	for(int j = 0; j < T; j++){
		int v = Y[j];
		qry[dep[tail[v]]].pb({tail[v], d[v] - d[tail[v]], 1});
	}
	int ans = inf;
	for(int j = n - 1; j >= 0; j--){
		vector<state> tmp;
		sort(qry[j].begin(), qry[j].end());
		for(auto k : qry[j]){
			bool used = false;
			if(tmp.size() >= 1 && tmp.back().v == k.v && tmp.back().colour + k.colour == 1) ans = min(ans, tmp.back().dis + k.dis);
			if(tmp.size() >= 2 && tmp[tmp.size() - 2].v == k.v && tmp[tmp.size() - 2].colour + k.colour == 1) ans = min(ans, tmp[tmp.size() - 2].dis + k.dis);
			if(tmp.size() >= 1 && tmp[tmp.size() - 1].v == k.v && tmp[tmp.size() - 1].colour == k.colour){
				tmp[tmp.size() - 1].dis = min(tmp[tmp.size() - 1].dis, k.dis); used = true;
			}
			if(tmp.size() >= 2 && tmp[tmp.size() - 2].v == k.v && tmp[tmp.size() - 2].colour == k.colour){
				tmp[tmp.size() - 2].dis = min(tmp[tmp.size() - 2].dis, k.dis); used = true;
			}
			if(!used){
				tmp.pb(k);
			}
		}
		if(j > 0){
			for(auto k : tmp){
				qry[j - 1].pb({p[k.v], k.dis + d[k.v] - d[p[k.v]], k.colour});
			}
		}
	}
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(long long int, long long int)':
factories.cpp:15:15: warning: variable 'son' set but not used [-Wunused-but-set-variable]
   15 |  int out = 0, son = -1;
      |               ^~~
factories.cpp: In function 'long long int Query(long long int, long long int*, long long int, long long int*)':
factories.cpp:58:14: error: 'n' was not declared in this scope
   58 |  for(int j = n - 1; j >= 0; j--) qry[j].clear();
      |              ^
factories.cpp:68:14: error: 'n' was not declared in this scope
   68 |  for(int j = n - 1; j >= 0; j--){
      |              ^