Submission #554071

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

factories

#include "factories.h"		#include "factories.h"
#include <bits/stdc++.h>		#include <bits/stdc++.h>
#define int long long		#define int long long
#define fi first		#define fi first
#define se second		#define se second
#define pb push_back		#define pb push_back
#define mp make_pair		#define mp make_pair
using namespace std;		using namespace std;
typedef pair<int, int> pii;		typedef pair<int, int> pii;
const int N = 1e4 + 13, L = 20;		const int N = 5e5 + 13, L = 20;
const int inf = 1LL << 60;		const int inf = 1LL << 60;
int d[N], p[N], dep[N], sz[N];		int d[N], p[N], dep[N], sz[N];
vector<pii> G[N];		vector<pii> G[N];
int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];		int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];
int euler[N], euler2[N * 2];		int euler[N], euler2[N * 2];
int st[N][L];		int st[N][L];
int n;		int n;
 		
void dfs(int v, int par = -1){		void dfs(int v, int par = -1){
	euler[timer] = v, op[v] = timer++, sz[v] = 1;			euler[timer] = v, op[v] = timer++, sz[v] = 1;
	euler2[timer2] = v, op2[v] = timer2++;			euler2[timer2] = v, op2[v] = timer2++;
	int out = 0, son = -1;			int out = 0, son = -1;
	for(auto i : G[v]){			for(auto i : G[v]){
		if(i.fi != par){				if(i.fi != par){
			d[i.fi] = d[v] + i.se;					d[i.fi] = d[v] + i.se;
			p[i.fi] = v;					p[i.fi] = v;
			dep[i.fi] = dep[v] + 1;					dep[i.fi] = dep[v] + 1;
			dfs(i.fi, v);					dfs(i.fi, v);
			euler2[timer2++] = v;					euler2[timer2++] = v;
			out++; son = i.fi;					out++; son = i.fi;
			sz[v] += sz[i.fi];					sz[v] += sz[i.fi];
		}				}
	}			}
	ed[v] = timer;			ed[v] = timer;
	ed2[v] = timer2 - 1;			ed2[v] = timer2 - 1;
}		}
 		
struct Fenwick{		struct Fenwick{
	int bit[N];			int bit[N];
	void upd(int p, int v){			void upd(int p, int v){
		p++;				p++;
		for(int i = p; i < N; i += i & -i){				for(int i = p; i < N; i += i & -i){
			bit[i] += v;					bit[i] += v;
		}				}
	}	
	int qry(int p){	
		p++;	
		int ret = 0;	
		for(int i = p; i; i -= i & -i){	
			ret += bit[i];	
		}	
		return ret;	
	}	
		
	int qry_pos(int v){ // 1-base, >= 1	
		int ret = 0, val = 0;	
		for(int j = 19; j >= 0; j--){	
			if(ret + (1 << j) >= N) continue;	
			if(val + bit[ret + (1 << j)] < v) val += bit[ret + (1 << j)], ret += (1 << j);	
		}	
		return ret;	
	}	
} c0, c1;	
 	
void bl(int n){	
	for(int i = 0; i < n * 2 - 1; i++) st[i][0] = euler2[i];	
	for(int j = 1; j < 20; j++){	
		for(int i = 0; i <= n * 2 - 1 - (1 << j); i++){	
			st[i][j] = dep[st[i][j - 1]] < dep[st[i + (1 << j - 1)][j - 1]] ? st[i][j - 1] : st[i + (1 << j - 1)][j - 1];	
		}	
	}	
}	
 	
int lca(int x, int y){	
	int a = min(op2[x], op2[y]), b = max(ed2[x], ed2[y]);	
	int l = __lg(b - a + 1);	
	int ret = dep[st[a][l]] < dep[st[b - (1 << l) + 1][l]] ? st[a][l] : st[b - (1 << l) + 1][l];	
	return ret;	
}	
 	
struct state{	
	int v, dis, colour;	
	bool operator< (const state& o) const{	
		return v < o.v;	
	}	
};	
 	
vector<state> qry[N];	
 	
void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {	
	n = N;	
	for(int i = 0; i < N - 1; i++){	
		G[B[i]].pb({A[i], D[i]});	
		G[A[i]].pb({B[i], D[i]});	
	}	
	dfs(0);	
	bl(N);	
}	
 	
long long Query(int32_t S, int32_t X[], int32_t T, int32_t 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[v]].pb({v, d[v] - d[v], 0});	
	}	
	for(int j = 0; j < T; j++){	
		int v = Y[j];	
		qry[dep[v]].pb({v, d[v] - d[v], 1});	
	}	
	for(int j = 0; j < S; j++) c0.upd(op[X[j]], 1);	
	for(int j = 0; j < T; j++) c1.upd(op[Y[j]], 1);	
	int ans = inf;	
	for(j; pq.size();){
		j = pq.top(); pq.pop(); in_pq[j] = false;
		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){	
				int _lca = 0;	
				if(k.colour){	
					int l = c0.qry_pos(c0.qry(op[k.v] - 1)), r = c0.qry_pos(c0.qry(op[k.v] + sz[k.v] - 1) + 1);	
					if(l < 0 && r > n - 1) _lca = 0;	
					else if(l < 0 || r > n - 1) _lca = l < 0 ? lca(k.v, euler[r]) : lca(euler[l], k.v);	
					else{	
						int llca = lca(euler[l], k.v), rlca = lca(k.v, euler[r]);	
						_lca = (dep[llca] > dep[rlca] ? llca : rlca);	
					}	
						
				}else{	
					int l = c1.qry_pos(c1.qry(op[k.v] - 1)), r = c1.qry_pos(c1.qry(op[k.v] + sz[k.v] - 1) + 1);	
					if(l < 0 && r > n - 1) _lca = 0;	
					else if(l < 0 || r > n - 1) _lca = l < 0 ? lca(k.v, euler[r]) : lca(euler[l], k.v);	
					else{	
						int llca = lca(euler[l], k.v), rlca = lca(k.v, euler[r]);	
						_lca = (dep[llca] > dep[rlca] ? llca : rlca);	
					}	
				}	
				if(_lca == k.v) _lca = p[k.v];
				if(!in_pq[dep[_lca]]) in_pq[dep[_lca]] = true, qry[dep[_lca]].clear(), pq.push(dep[_lca]);
				qry[dep[_lca]].pb({_lca, k.dis + d[k.v] - d[_lca], k.colour});
			}	
		}	
	}	
	for(int j = 0; j < S; j++) c0.upd(op[X[j]], -1);	
	for(int j = 0; j < T; j++) c1.upd(op[Y[j]], -1);	
	return ans;	
}

Compilation message (stderr)

factories.cpp:1:25: warning: extra tokens at end of #include directive
    1 | #include "factories.h"  #include "factories.h"
      |                         ^
factories.cpp:2:27: warning: extra tokens at end of #include directive
    2 | #include <bits/stdc++.h>  #include <bits/stdc++.h>
      |                           ^
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:9:14: note: in expansion of macro 'int'
    9 | typedef pair<int, int> pii;  typedef pair<int, int> pii;
      |              ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:9:19: note: in expansion of macro 'int'
    9 | typedef pair<int, int> pii;  typedef pair<int, int> pii;
      |                   ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:9:43: note: in expansion of macro 'int'
    9 | typedef pair<int, int> pii;  typedef pair<int, int> pii;
      |                                           ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:9:48: note: in expansion of macro 'int'
    9 | typedef pair<int, int> pii;  typedef pair<int, int> pii;
      |                                                ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:10:7: note: in expansion of macro 'int'
   10 | const int N = 1e4 + 13, L = 20;  const int N = 5e5 + 13, L = 20;
      |       ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:10:40: note: in expansion of macro 'int'
   10 | const int N = 1e4 + 13, L = 20;  const int N = 5e5 + 13, L = 20;
      |                                        ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:11:7: note: in expansion of macro 'int'
   11 | const int inf = 1LL << 60;  const int inf = 1LL << 60;
      |       ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:11:35: note: in expansion of macro 'int'
   11 | const int inf = 1LL << 60;  const int inf = 1LL << 60;
      |                                   ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:12:1: note: in expansion of macro 'int'
   12 | int d[N], p[N], dep[N], sz[N];  int d[N], p[N], dep[N], sz[N];
      | ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:12:33: note: in expansion of macro 'int'
   12 | int d[N], p[N], dep[N], sz[N];  int d[N], p[N], dep[N], sz[N];
      |                                 ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:14:1: note: in expansion of macro 'int'
   14 | int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];  int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];
      | ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:14:75: note: in expansion of macro 'int'
   14 | int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];  int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];
      |                                                                           ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:15:1: note: in expansion of macro 'int'
   15 | int euler[N], euler2[N * 2];  int euler[N], euler2[N * 2];
      | ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:15:31: note: in expansion of macro 'int'
   15 | int euler[N], euler2[N * 2];  int euler[N], euler2[N * 2];
      |                               ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:16:1: note: in expansion of macro 'int'
   16 | int st[N][L];  int st[N][L];
      | ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:16:16: note: in expansion of macro 'int'
   16 | int st[N][L];  int st[N][L];
      |                ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:17:1: note: in expansion of macro 'int'
   17 | int n;  int n;
      | ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:17:9: note: in expansion of macro 'int'
   17 | int n;  int n;
      |         ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:19:10: note: in expansion of macro 'int'
   19 | void dfs(int v, int par = -1){  void dfs(int v, int par = -1){
      |          ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:19:17: note: in expansion of macro 'int'
   19 | void dfs(int v, int par = -1){  void dfs(int v, int par = -1){
      |                 ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:19:42: note: in expansion of macro 'int'
   19 | void dfs(int v, int par = -1){  void dfs(int v, int par = -1){
      |                                          ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:19:49: note: in expansion of macro 'int'
   19 | void dfs(int v, int par = -1){  void dfs(int v, int par = -1){
      |                                                 ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:22:2: note: in expansion of macro 'int'
   22 |  int out = 0, son = -1;   int out = 0, son = -1;
      |  ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:22:27: note: in expansion of macro 'int'
   22 |  int out = 0, son = -1;   int out = 0, son = -1;
      |                           ^~~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:24:8: note: in expansion of macro 'fi'
   24 |   if(i.fi != par){    if(i.fi != par){
      |        ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:24:28: note: in expansion of macro 'fi'
   24 |   if(i.fi != par){    if(i.fi != par){
      |                            ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:25:8: note: in expansion of macro 'fi'
   25 |    d[i.fi] = d[v] + i.se;     d[i.fi] = d[v] + i.se;
      |        ^~
factories.cpp:5:20: error: stray '#' in program
    5 | #define se second  #define se second
      |                    ^
factories.cpp:25:23: note: in expansion of macro 'se'
   25 |    d[i.fi] = d[v] + i.se;     d[i.fi] = d[v] + i.se;
      |                       ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:25:35: note: in expansion of macro 'fi'
   25 |    d[i.fi] = d[v] + i.se;     d[i.fi] = d[v] + i.se;
      |                                   ^~
factories.cpp:5:20: error: stray '#' in program
    5 | #define se second  #define se second
      |                    ^
factories.cpp:25:50: note: in expansion of macro 'se'
   25 |    d[i.fi] = d[v] + i.se;     d[i.fi] = d[v] + i.se;
      |                                                  ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:26:8: note: in expansion of macro 'fi'
   26 |    p[i.fi] = v;     p[i.fi] = v;
      |        ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:26:25: note: in expansion of macro 'fi'
   26 |    p[i.fi] = v;     p[i.fi] = v;
      |                         ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:27:10: note: in expansion of macro 'fi'
   27 |    dep[i.fi] = dep[v] + 1;     dep[i.fi] = dep[v] + 1;
      |          ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:27:38: note: in expansion of macro 'fi'
   27 |    dep[i.fi] = dep[v] + 1;     dep[i.fi] = dep[v] + 1;
      |                                      ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:28:10: note: in expansion of macro 'fi'
   28 |    dfs(i.fi, v);     dfs(i.fi, v);
      |          ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:28:28: note: in expansion of macro 'fi'
   28 |    dfs(i.fi, v);     dfs(i.fi, v);
      |                            ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:30:19: note: in expansion of macro 'fi'
   30 |    out++; son = i.fi;     out++; son = i.fi;
      |                   ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:30:42: note: in expansion of macro 'fi'
   30 |    out++; son = i.fi;     out++; son = i.fi;
      |                                          ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:31:18: note: in expansion of macro 'fi'
   31 |    sz[v] += sz[i.fi];     sz[v] += sz[i.fi];
      |                  ^~
factories.cpp:4:19: error: stray '#' in program
    4 | #define fi first  #define fi first
      |                   ^
factories.cpp:31:41: note: in expansion of macro 'fi'
   31 |    sz[v] += sz[i.fi];     sz[v] += sz[i.fi];
      |                                         ^~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:39:2: note: in expansion of macro 'int'
   39 |  int bit[N];   int bit[N];
      |  ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:39:16: note: in expansion of macro 'int'
   39 |  int bit[N];   int bit[N];
      |                ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:40:11: note: in expansion of macro 'int'
   40 |  void upd(int p, int v){   void upd(int p, int v){
      |           ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:40:18: note: in expansion of macro 'int'
   40 |  void upd(int p, int v){   void upd(int p, int v){
      |                  ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:40:37: note: in expansion of macro 'int'
   40 |  void upd(int p, int v){   void upd(int p, int v){
      |                                     ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:40:44: note: in expansion of macro 'int'
   40 |  void upd(int p, int v){   void upd(int p, int v){
      |                                            ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:42:7: note: in expansion of macro 'int'
   42 |   for(int i = p; i < N; i += i & -i){    for(int i = p; i < N; i += i & -i){
      |       ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:42:46: note: in expansion of macro 'int'
   42 |   for(int i = p; i < N; i += i & -i){    for(int i = p; i < N; i += i & -i){
      |                                              ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:46:2: note: in expansion of macro 'int'
   46 |  int qry(int p){
      |  ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:46:10: note: in expansion of macro 'int'
   46 |  int qry(int p){
      |          ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:48:3: note: in expansion of macro 'int'
   48 |   int ret = 0;
      |   ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:49:7: note: in expansion of macro 'int'
   49 |   for(int i = p; i; i -= i & -i){
      |       ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:55:2: note: in expansion of macro 'int'
   55 |  int qry_pos(int v){ // 1-base, >= 1
      |  ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:55:14: note: in expansion of macro 'int'
   55 |  int qry_pos(int v){ // 1-base, >= 1
      |              ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:56:3: note: in expansion of macro 'int'
   56 |   int ret = 0, val = 0;
      |   ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:57:7: note: in expansion of macro 'int'
   57 |   for(int j = 19; j >= 0; j--){
      |       ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:65:9: note: in expansion of macro 'int'
   65 | void bl(int n){
      |         ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:66:6: note: in expansion of macro 'int'
   66 |  for(int i = 0; i < n * 2 - 1; i++) st[i][0] = euler2[i];
      |      ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:67:6: note: in expansion of macro 'int'
   67 |  for(int j = 1; j < 20; j++){
      |      ^~~
factories.cpp:3:24: error: stray '#' in program
    3 | #define int long long  #define int long long
      |                        ^
factories.cpp:68:7: note: in expansion of macro 'int'
   68 |   for(int i = 0; i <= n * 2 - 1 - (1 << j); i++){
      |       ^~~
factories.cpp:3:24: error: stray '#' in program