oj.uz

Submission #99721

# Submission time Handle Problem Language Result Execution time Memory
99721 2019-03-06T08:44:16 Z cki86201 Unique Cities (JOI19_ho_t5) C++11
32 / 100
 680 ms 38676 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];

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

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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Incorrect 9 ms 6784 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 14536 KB Output is correct
2 Correct 334 ms 25108 KB Output is correct
3 Correct 39 ms 9916 KB Output is correct
4 Correct 508 ms 20316 KB Output is correct
5 Correct 680 ms 38676 KB Output is correct
6 Correct 583 ms 29460 KB Output is correct
7 Correct 440 ms 20240 KB Output is correct
8 Correct 472 ms 22132 KB Output is correct
9 Correct 499 ms 21540 KB Output is correct
10 Correct 482 ms 21408 KB Output is correct
11 Correct 235 ms 20920 KB Output is correct
12 Correct 525 ms 31784 KB Output is correct
13 Correct 480 ms 29364 KB Output is correct
14 Correct 518 ms 28724 KB Output is correct
15 Correct 224 ms 20776 KB Output is correct
16 Correct 512 ms 33048 KB Output is correct
17 Correct 536 ms 29608 KB Output is correct

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Incorrect 9 ms 6784 KB Output isn't correct
3 Halted 0 ms 0 KB -