Submission #99740

#	Time	Username	Problem	Language	Result	Execution time	Memory
99740		cki86201	Unique Cities (JOI19_ho_t5)	C++11	100 / 100	1826 ms	70968 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];
int ST[200020], EN[200020], cs, rev[200020];
int par[200020];
int Q[200020];
int nxt[200020][20];

void pdfs(int x, int fa) {
	mxdep[x] = dep[x];
	ST[x] = ++cs; rev[cs] = x;
	int mxl[2] = {};
	for(int e : E[x]) if(e != fa) {
		dep[e] = dep[x] + 1;
		par[e] = x;
		pdfs(e, x);
		if(mxdep[x] < mxdep[e]) mxdep[x] = mxdep[e], nxt[x][0] = e;
		int L = mxdep[e] - dep[x];
		if(mxl[0] < L) mxl[1] = mxl[0], mxl[0] = L;
		else if(mxl[1] < L) mxl[1] = L;
	}
	int len = mxl[1];
	if(len) {
		int t = x;
		rep(j, len) Q[t] = 1, t = par[t];
	}
	EN[x] = cs;
}

int get_nxt(int x, int p) {
	rep(i, 20) if(1<<i & p) x = nxt[x][i];
	return x;
}

int C[200020];
vector <int> H[200020];
int cnt[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<=N;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}) {
		cs = 0;
		for(int i=1;i<=N;i++) {
			Q[i] = 0;
			rep(j, 20) nxt[i][j] = 0;
			H[i].clear();
		}
		dep[rt] = 0;
		pdfs(rt, -1);
		for(int j=1;j<20;j++) {
			for(int i=1;i<=N;i++) nxt[i][j] = nxt[ nxt[i][j-1] ][j-1];
		}
		for(int i=1;i<=N;i++) if(Q[i] == 0 && i != rt) {
			int L = mxdep[i] - dep[i];
			int ni = get_nxt(i, (L + 1) / 2);
			H[ST[ni]].pb(C[par[i]]);
			H[EN[ni]+1].pb(-C[par[i]]);
		}
		for(int i=1;i<=M;i++) cnt[i] = 0;
		int res = 0;
		for(int i=1;i<=N;i++) {
			for(int e : H[i]) {
				if(e > 0) res += (cnt[e] == 0), ++cnt[e];
				else res -= (cnt[-e] == 1), --cnt[-e];
			}
			X[tt][rev[i]] = res;
		}
		++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:89: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:91: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:94:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%d", C + i);
                        ~~~~~^~~~~~~~~~~~~

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