Submission #99721

#	Time	Username	Problem	Language	Result	Execution time	Memory
99721		cki86201	Unique Cities (JOI19_ho_t5)	C++11	32 / 100	680 ms	38676 KiB

joi2019_ho_t5

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, M;
vector <int> E[200020];

int dis[2][200020];
int far(int t, int x) {
	vector <int> q;
	q.pb(x);
	for(int i=1;i<=N;i++) dis[t][i] = -1;
	dis[t][x] = 0;
	rep(i, szz(q)) {
		int a = q[i];
		for(int e : E[a]) if(dis[t][e] == -1) {
			dis[t][e] = dis[t][a] + 1;
			q.pb(e);
		}
	}
	return q.back();
}

int ans[200020];
int dep[200020], mxdep[200020];

void pdfs(int x, int fa) {
	mxdep[x] = dep[x];
	for(int e : E[x]) if(e != fa) {
		dep[e] = dep[x] + 1;
		pdfs(e, x);
		mxdep[x] = max(mxdep[x], mxdep[e]);
	}
}

void DFS(int x, int fa, int T[], int min_uni) {
	pii mxx[2] = {};
	rep(u, 2) mxx[u] = pii((int)-1e9, -1);
	for(int e : E[x]) if(e != fa) {
		int L = mxdep[e] - dep[x];
		if(mxx[0].Fi < L) mxx[1] = mxx[0], mxx[0] = pii(L, e);
		else if(mxx[1].Fi < L) mxx[1] = pii(L, e);
	}
	for(int e : E[x]) if(e != fa) {
		int nu = min_uni;
		int g = -1;
		if(mxx[0].Se != e) g = mxx[0].Fi;
		else g = mxx[1].Fi;
		if(g >= 1 && min_uni >= dep[x] - g) nu = dep[x];
		int L1 = mxdep[e] - dep[e];
		int L2 = dep[e] - nu;
		if(L1 < L2) T[e] = 1;
		DFS(e, x, T, nu);
	}
}

int C[200020];

int main() {
	scanf("%d%d", &N, &M);
	for(int i=1;i<N;i++) {
		int x, y; scanf("%d%d", &x, &y);
		E[x].pb(y); E[y].pb(x);
	}
	for(int i=1;i<=M;i++) scanf("%d", C + i);
	int a = far(0, 1);
	int b = far(0, a);
	far(1, b);
	int tt = 0;
	int X[2][200020] = {};
	for(int rt : {a, b}) {
		dep[rt] = 0;
		pdfs(rt, -1);
		DFS(rt, -1, X[tt], 0);
		++tt;
	}
	for(int i=1;i<=N;i++) {
		if(dis[0][i] >= dis[1][i]) ans[i] = X[0][i];
		else ans[i] = X[1][i];
	}
	for(int i=1;i<=N;i++) printf("%d\n", ans[i]);
	
	return 0;
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:92:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=M;i++) scanf("%d", C + i);
                        ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 32 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32