oj.uz

Submission #99737

# Submission time Handle Problem Language Result Execution time Memory
99737 2019-03-06T11:15:20 Z cki86201 Unique Cities (JOI19_ho_t5) C++11
32 / 100
 1626 ms 72356 KB 
#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<=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}) {
		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

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<=M;i++) scanf("%d", C + i);
                        ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 11392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 403 ms 32660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 41628 KB Output is correct
2 Correct 1626 ms 69856 KB Output is correct
3 Correct 108 ms 19180 KB Output is correct
4 Correct 880 ms 52916 KB Output is correct
5 Correct 1613 ms 72356 KB Output is correct
6 Correct 1102 ms 60224 KB Output is correct
7 Correct 1082 ms 53224 KB Output is correct
8 Correct 982 ms 56988 KB Output is correct
9 Correct 1010 ms 55712 KB Output is correct
10 Correct 947 ms 54432 KB Output is correct
11 Correct 874 ms 53264 KB Output is correct
12 Correct 1405 ms 68112 KB Output is correct
13 Correct 1114 ms 61360 KB Output is correct
14 Correct 1237 ms 60500 KB Output is correct
15 Correct 746 ms 54012 KB Output is correct
16 Correct 1271 ms 66864 KB Output is correct
17 Correct 1177 ms 61208 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 11392 KB Output isn't correct
2 Halted 0 ms 0 KB -