제출 #481905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
481905		MilosMilutinovic	공장들 (JOI14_factories)	C++14	0 / 100	20 ms	24268 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){
	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;
			dub[c.xx] = dub[u] + 1;
			dfs(c.xx, u);
		}
	}
}

int lca(int u, int v){
	if(dub[u] < dub[v])swap(u, v);
	ff(i,1,22){
		if(dub[par[u][i]] <= dub[v])u = par[u][i];
	}
	ff(i,1,22){
		if(par[u][i] != par[v][i]){
			u = par[u][i];
			v = par[v][i];
		}
	}
	if(u != v)u = par[u][0];
	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({B[i], D[i]});
	}
	dfs(1, 0);
	decomp(1);

	ff(i,1,n)mn[i] = 1e18;
}


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]++;
	vector<int> cv;
	ff(i,0,S-1){
		for(auto c:cale[X[i]]){
			mn[c] = min(mn[c], dist(X[i], c));
			cv.pb(c);
		}
	}
	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;
	return ans;
}

컴파일 시 표준 에러 (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:23:2: note: in expansion of macro 'ff'
   23 |  ff(i,1,22) par[u][i] = par[par[u][i - 1]][i - 1];
      |  ^~
factories.cpp: In function 'int lca(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:35:2: note: in expansion of macro 'ff'
   35 |  ff(i,1,22){
      |  ^~
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:38:2: note: in expansion of macro 'ff'
   38 |  ff(i,1,22){
      |  ^~
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:99:2: note: in expansion of macro 'ff'
   99 |  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:108:2: note: in expansion of macro 'ff'
  108 |  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:114:2: note: in expansion of macro 'ff'
  114 |  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:115:2: note: in expansion of macro 'ff'
  115 |  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:117:2: note: in expansion of macro 'ff'
  117 |  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:123:2: note: in expansion of macro 'ff'
  123 |  ff(i,0,T-1){
      |  ^~

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