Submission #481976

#	Time	Username	Problem	Language	Result	Execution time	Memory
481976		MilosMilutinovic	Factories (JOI14_factories)	C++14	0 / 100	47 ms	48800 KiB

factories

#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pb push_back
#define xx first
#define yy second
#define pii pair<int,int>
#define ll long long

using namespace std;

int n;
int sajz[500005];
int par[500005][23];
vector<pii> graf[500005];
bool was[500005];
vector<int> cale[500005];
int dub[500005];
ll dep[500005];

void dfs(int u, int p){
	dub[u] = dub[p] + 1;
	par[u][0] = p;
	ff(i,1,22) par[u][i] = par[par[u][i - 1]][i - 1];
	for(auto c:graf[u]){
		if(c.xx != p){
			dep[c.xx] = dep[u] + c.yy;
			dfs(c.xx, u);
		}
	}
}

int lca(int u, int v){
	if(dub[u] < dub[v])swap(u, v);
	fb(i,22,0){
		if(dub[par[u][i]] >= dub[v])u = par[u][i];
	}
	//cout << u << " " << v << "\n";
	assert(dub[u] == dub[v]);
	fb(i,22,0){
		if(par[u][i] != par[v][i]){
			u = par[u][i];
			v = par[v][i];
		}
	}
	if(u != v){
		u = par[u][0];
		v = par[v][0];
	}
	assert(u == v);
	return u;
}

ll dist(int u, int v){
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void dfs1(int u, int p){
	sajz[u] = 1;
	for(auto c:graf[u]){
		if(c.xx == p || was[c.xx]) {
			continue;
		}
		dfs1(c.xx, u);
		sajz[u] += sajz[c.xx];
	}
}

int dfs2(int u, int p, int n){
	for(auto c:graf[u]){
		if(!was[c.xx] && c.xx != p && sajz[c.xx] * 2 >= n) {
			return dfs2(c.xx, u, n);
		}
	}
	return u;
}

int findcen(int u){
	dfs1(u, u);
	return dfs2(u, u, sajz[u]);
}

void solve(int u, int p, int st){
	cale[u].pb(st);
	for(auto c:graf[u]){
		if(c.xx != p && !was[c.xx]){
			solve(c.xx, u, st);
		}
	}
}

void decomp(int u) {
	u = findcen(u);
	solve(u, u, u);
	was[u] = true;
	for(auto c:graf[u]){
		if(!was[c.xx])decomp(c.xx);
	}
}

ll mn[500005];

void Init(int N, int* A, int* B, int* D){
	n = N;
	ff(i,0,n-2){
		A[i]++;
		B[i]++;
		graf[A[i]].pb({B[i], D[i]});
		graf[B[i]].pb({A[i], D[i]});
	}
	dfs(1, 0);
	decomp(1);
    ff(i,1,n) assert((int) cale[i].size() <= 50);
	ff(i,1,n)mn[i] = 1e18;
}

bool kurcina[500005];

ll Query(int S, int* X, int T, int* Y){
	ll ans = 1e18;
	ff(i,0,S-1)X[i]++;
	ff(i,0,T-1)Y[i]++;
//	ff(i,0,S-1) ff(j,0,T-1) ans = min(ans, dist(X[i], Y[j]));
	vector<int> cv;
	ff(i,0,S-1){
		for(auto c:cale[X[i]]){
			mn[c] = min(mn[c], dist(X[i], c));
			if(!kurcina[c])cv.pb(c),kurcina[c] = true;
		}
	}
	ff(i,0,T-1){
		for(auto c:cale[Y[i]]){
			ans = min(ans, mn[c] + dist(c, Y[i]));
		}
	}
	for(auto c:cv)mn[c] = 1e18, kurcina[c] = false;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:24:2: note: in expansion of macro 'ff'
   24 |  ff(i,1,22) par[u][i] = par[par[u][i - 1]][i - 1];
      |  ^~
factories.cpp: In function 'int lca(int, int)':
factories.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
factories.cpp:35:2: note: in expansion of macro 'fb'
   35 |  fb(i,22,0){
      |  ^~
factories.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
factories.cpp:40:2: note: in expansion of macro 'fb'
   40 |  fb(i,22,0){
      |  ^~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:105:2: note: in expansion of macro 'ff'
  105 |  ff(i,0,n-2){
      |  ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:113:5: note: in expansion of macro 'ff'
  113 |     ff(i,1,n) assert((int) cale[i].size() <= 50);
      |     ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:114:2: note: in expansion of macro 'ff'
  114 |  ff(i,1,n)mn[i] = 1e18;
      |  ^~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:121:2: note: in expansion of macro 'ff'
  121 |  ff(i,0,S-1)X[i]++;
      |  ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:122:2: note: in expansion of macro 'ff'
  122 |  ff(i,0,T-1)Y[i]++;
      |  ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:125:2: note: in expansion of macro 'ff'
  125 |  ff(i,0,S-1){
      |  ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:131:2: note: in expansion of macro 'ff'
  131 |  ff(i,0,T-1){
      |  ^~
factories.cpp:137:1: warning: no return statement in function returning non-void [-Wreturn-type]
  137 | }
      | ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67