Submission #1230751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230751		balls	Factories (JOI14_factories)	C++20	Compilation error	0 ms	0 KiB

factories

#pragma GCC optimize("Ofast")

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;

const int MaxN = 5e5 + 7;
const int Log = 20;
vector<int> g[MaxN];
vector<long long> c[MaxN];
int p[MaxN], in[MaxN], arr[MaxN], d[MaxN], n, sz, cn, gl;
long long be[MaxN][Log], opt[MaxN];
bool vc[MaxN];

int dfssz(int s, int f) {
	int x = 1;
	for (int i = 0; i < g[s].size(); i++) {
	    if (g[s][i] != f && !vc[g[s][i]]) {
	        x += dfssz(g[s][i], s);
	    }
	}
	return x;
}

int dfsc(int s, int f) {
	int x = 1;
	bool ce = true;
	for (int i = 0; i < g[s].size(); i++) {
	    if (g[s][i] != f && !vc[g[s][i]]) {
    		int a = dfsc(g[s][i], s);
    		if (a > sz / 2) {
    		    ce=false;
    		}
    		x += a;
    	}
	if (sz - x > sz / 2) {
	    ce = false;
	}
	if (ce) {
	    cn = s;
	}
	return x;
}

void dfs(int s, int f, long long dist, int po) {
	if (d[s] < d[po]) {
	    return;
	}
	be[s][d[s] - d[po]] = dist;
	for (int i = 0; i < g[s].size(); i++) {
	    if (g[s][i] != f) {
	        dfs(g[s][i], s, dist + c[s][i], po);
	    }
	}
}

void comp(int s, int f, int du) {
	sz = dfssz(s, -1);
	dfsc(s, -1);
	p[cn] = f;
	vc[cn] = true;
	d[cn] = du;
	int tmp = cn;
	for (int i = 0; i < g[tmp].size(); i++) {
	    if (!vc[g[tmp][i]]) {
	        comp(g[tmp][i], tmp, du + 1);
	    }
	}
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	int root;
	for (int i = 0; i < n - 1; i++) {
	    g[A[i]].push_back(B[i]);
	    g[B[i]].push_back(A[i]);
	    c[A[i]].push_back(D[i]);
	    c[B[i]].push_back(D[i]);
	}
	comp(0, -1, 0);
	for (int i = 0; i < n; i++) {
	    dfs(i, -1, 0, i);
	}
	fill(opt, opt + MaxN, 1e18);
}

long long Query(int S, int X[], int T, int Y[]) {
	int s = S, t = T;
	long long sk = 1e18;
	for (int i = 0; i < s; i++) {
		int a = X[i];
		cnt = 0;
		while (a != -1) {
		    opt[a] = min(opt[a], be[X[i]][cnt]);
		    a = p[a];
		    cnt++;
		}
	}
	for (int i = 0; i < t; i++) {
		int a = Y[i];
		cnt = 0;
		while (a != -1) {
		    sk = min(sk, be[Y[i]][cnt] + opt[a]);
		    a = p[a];
		    cnt++;
		}
	}
	for (int i = 0; i < s; i++) {
		int a = X[i];
		while (a != -1) {
		    opt[a] = 1e18;
		    a = p[a];
		}
	}
	return sk;
}

Compilation message (stderr)

factories.cpp: In function 'int dfsc(int, int)':
factories.cpp:45:48: error: a function-definition is not allowed here before '{' token
   45 | void dfs(int s, int f, long long dist, int po) {
      |                                                ^
factories.cpp:57:33: error: a function-definition is not allowed here before '{' token
   57 | void comp(int s, int f, int du) {
      |                                 ^
factories.cpp:71:45: error: a function-definition is not allowed here before '{' token
   71 | void Init(int N, int A[], int B[], int D[]) {
      |                                             ^
factories.cpp:87:49: error: a function-definition is not allowed here before '{' token
   87 | long long Query(int S, int X[], int T, int Y[]) {
      |                                                 ^
factories.cpp:116:2: error: expected '}' at end of input
  116 | }
      |  ^
factories.cpp:25:24: note: to match this '{'
   25 | int dfsc(int s, int f) {
      |                        ^
factories.cpp:116:2: warning: control reaches end of non-void function [-Wreturn-type]
  116 | }
      |  ^