oj.uz

Submission #226629

# Submission time Handle Problem Language Result Execution time Memory
226629 2020-04-24T15:17:16 Z stefdasca City Mapping (NOI18_citymapping) C++14
100 / 100
 22 ms 640 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
 
long long dist[1002];

bool cmp(int a, int b)
{
	return dist[a] < dist[b];
}
int rad = 1;
vector<int> v[1002];
int sts[1002], nu[1002];
void dfs(int dad, int nod)
{
	sts[nod] = 1;
	for(int i = 0; i < v[nod].size(); ++i)
	{
		int vecin = v[nod][i];
		if(vecin == dad)
			continue;
		dfs(nod, vecin);
		sts[nod] += sts[vecin];
	}
}
int bgL(int nod)
{
	bool ok = 1;
	int bst = 0;
	for(int i = 0; i < v[nod].size(); ++i)
	{
		int vecin = v[nod][i];
		if(sts[vecin] > sts[nod] || nu[vecin])
			continue;
		ok = 0;
		if(sts[vecin] > sts[bst])
			bst = vecin;
	}
	if(ok)
		return nod;
	return bgL(bst);
}
int bgg;
int optnd(int nod, long long dst)
{
	if(dist[nod] - dist[bgg] == dst)
		return nod;
	int bst = 0;
	for(int i = 0; i < v[nod].size(); ++i)
	{
		int vecin = v[nod][i];
		if(sts[vecin] > sts[nod] || nu[vecin])
			continue;
		if(sts[vecin] > sts[bst])
			bst = vecin;
	}
	return optnd(bst, dst);
}
int bstson(int nod)
{
	int bst = 0;
	for(int i = 0; i < v[nod].size(); ++i)
	{
		int vecin = v[nod][i];
		if(sts[vecin] > sts[nod] || nu[vecin])
			continue;
		if(sts[vecin] > sts[bst])
			bst = vecin;
	}
	return bst;
}
int dfssz(int rt)
{
	int ans = 1;
	for(int i = 0; i < v[rt].size(); ++i)
	{
		int vecin = v[rt][i];
		if(sts[vecin] > sts[rt] || nu[vecin])
			continue;
		ans += dfssz(vecin);
	}
	return ans;
}
pair<int, int> solve(int nod, int pzx)
{
	int rt = 1;
	int lft = pzx;
	while(lft > 1)
	{
		int ans = bgL(rt);
		long long RL = abs(dist[ans] - dist[rt]);
		long long LX = get_distance(nod, ans);
		long long RX = abs(dist[nod] - dist[rt]);
		long long dvg = ((RL+RX) - LX) / 2;
		bgg = rt;
		int nxt = optnd(rt, dvg);
		nu[bstson(nxt)] = 1;
		rt = nxt;
		lft = dfssz(rt);
	}
	return {rt, dist[nod] - dist[rt]};
}
void find_roads(int n, int Q, int A[], int B[], int W[])
{
	dist[1] = 0;
	for(int i = 2; i <= n; ++i)
		dist[i] = get_distance(1, i);	
	int nr[1002];
	for(int i = 1; i <= n; ++i)
		nr[i] = i;
	sort(nr + 1, nr + n + 1, cmp);
	for(int i = 2; i <= n; ++i)
	{
		A[i-2] = nr[i];
		if(i != 2)
		{
			pair<int, int> ans = solve(nr[i], i-1);
			B[i-2] = ans.first;
			W[i-2] = ans.second;
		}
		else
		{
			B[i-2] = 1;
			W[i-2] = dist[nr[i]];
		}
		v[A[i-2]].push_back(B[i-2]);
		v[B[i-2]].push_back(A[i-2]);
		dfs(0, 1);
		memset(nu, 0, sizeof(nu));
	}
	return;
}

Compilation message

citymapping.cpp: In function 'void dfs(int, int)':
citymapping.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[nod].size(); ++i)
                 ~~^~~~~~~~~~~~~~~
citymapping.cpp: In function 'int bgL(int)':
citymapping.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[nod].size(); ++i)
                 ~~^~~~~~~~~~~~~~~
citymapping.cpp: In function 'int optnd(int, long long int)':
citymapping.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[nod].size(); ++i)
                 ~~^~~~~~~~~~~~~~~
citymapping.cpp: In function 'int bstson(int)':
citymapping.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[nod].size(); ++i)
                 ~~^~~~~~~~~~~~~~~
citymapping.cpp: In function 'int dfssz(int)':
citymapping.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[rt].size(); ++i)
                 ~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 512 KB Correct: 2678 out of 500000 queries used.
2 Correct 18 ms 512 KB Correct: 2420 out of 500000 queries used.
3 Correct 15 ms 512 KB Correct: 4534 out of 500000 queries used.
4 Correct 14 ms 512 KB Correct: 5523 out of 500000 queries used.
5 Correct 16 ms 512 KB Correct: 3383 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 512 KB Correct: 2678 out of 500000 queries used.
2 Correct 18 ms 512 KB Correct: 2420 out of 500000 queries used.
3 Correct 15 ms 512 KB Correct: 4534 out of 500000 queries used.
4 Correct 14 ms 512 KB Correct: 5523 out of 500000 queries used.
5 Correct 16 ms 512 KB Correct: 3383 out of 500000 queries used.
6 Correct 22 ms 640 KB Correct: 2009 out of 500000 queries used.
7 Correct 20 ms 640 KB Correct: 2063 out of 500000 queries used.
8 Correct 16 ms 640 KB Correct: 4244 out of 500000 queries used.
9 Correct 15 ms 512 KB Correct: 5089 out of 500000 queries used.
10 Correct 15 ms 512 KB Correct: 3054 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 640 KB Correct: 2090 out of 12000 queries used.
2 Correct 20 ms 640 KB Correct: 2318 out of 12000 queries used.
3 Correct 19 ms 512 KB Correct: 2470 out of 12000 queries used.
4 Correct 19 ms 640 KB Correct: 2440 out of 12000 queries used.
5 Correct 19 ms 640 KB Correct: 2231 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 640 KB Correct: 2090 out of 12000 queries used.
2 Correct 20 ms 640 KB Correct: 2318 out of 12000 queries used.
3 Correct 19 ms 512 KB Correct: 2470 out of 12000 queries used.
4 Correct 19 ms 640 KB Correct: 2440 out of 12000 queries used.
5 Correct 19 ms 640 KB Correct: 2231 out of 12000 queries used.
6 Correct 20 ms 640 KB Correct: 2473 out of 12000 queries used.
7 Correct 19 ms 640 KB Correct: 2382 out of 12000 queries used.
8 Correct 20 ms 640 KB Correct: 2207 out of 12000 queries used.
9 Correct 20 ms 640 KB Correct: 2235 out of 12000 queries used.
10 Correct 19 ms 512 KB Correct: 2302 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 512 KB Correct: 2678 out of 500000 queries used.
2 Correct 18 ms 512 KB Correct: 2420 out of 500000 queries used.
3 Correct 15 ms 512 KB Correct: 4534 out of 500000 queries used.
4 Correct 14 ms 512 KB Correct: 5523 out of 500000 queries used.
5 Correct 16 ms 512 KB Correct: 3383 out of 500000 queries used.
6 Correct 22 ms 640 KB Correct: 2009 out of 500000 queries used.
7 Correct 20 ms 640 KB Correct: 2063 out of 500000 queries used.
8 Correct 16 ms 640 KB Correct: 4244 out of 500000 queries used.
9 Correct 15 ms 512 KB Correct: 5089 out of 500000 queries used.
10 Correct 15 ms 512 KB Correct: 3054 out of 500000 queries used.
11 Correct 21 ms 640 KB Correct: 2090 out of 12000 queries used.
12 Correct 20 ms 640 KB Correct: 2318 out of 12000 queries used.
13 Correct 19 ms 512 KB Correct: 2470 out of 12000 queries used.
14 Correct 19 ms 640 KB Correct: 2440 out of 12000 queries used.
15 Correct 19 ms 640 KB Correct: 2231 out of 12000 queries used.
16 Correct 20 ms 640 KB Correct: 2473 out of 12000 queries used.
17 Correct 19 ms 640 KB Correct: 2382 out of 12000 queries used.
18 Correct 20 ms 640 KB Correct: 2207 out of 12000 queries used.
19 Correct 20 ms 640 KB Correct: 2235 out of 12000 queries used.
20 Correct 19 ms 512 KB Correct: 2302 out of 12000 queries used.
21 Correct 20 ms 512 KB Correct: 2502 out of 25000 queries used.
22 Correct 18 ms 640 KB Correct: 2071 out of 25000 queries used.
23 Correct 17 ms 512 KB Correct: 2285 out of 25000 queries used.
24 Correct 20 ms 640 KB Correct: 2036 out of 25000 queries used.
25 Correct 18 ms 512 KB Correct: 4436 out of 25000 queries used.
26 Correct 16 ms 512 KB Correct: 4358 out of 25000 queries used.
27 Correct 16 ms 512 KB Correct: 4307 out of 25000 queries used.
28 Correct 16 ms 512 KB Correct: 4417 out of 25000 queries used.
29 Correct 16 ms 512 KB Correct: 4502 out of 25000 queries used.
30 Correct 17 ms 512 KB Correct: 4442 out of 25000 queries used.
31 Correct 15 ms 512 KB Correct: 5151 out of 25000 queries used.
32 Correct 19 ms 640 KB Correct: 2223 out of 25000 queries used.
33 Correct 15 ms 512 KB Correct: 5083 out of 25000 queries used.
34 Correct 16 ms 640 KB Correct: 5158 out of 25000 queries used.
35 Correct 15 ms 512 KB Correct: 5100 out of 25000 queries used.
36 Correct 17 ms 512 KB Correct: 5118 out of 25000 queries used.
37 Correct 16 ms 512 KB Correct: 5144 out of 25000 queries used.
38 Correct 15 ms 512 KB Correct: 5102 out of 25000 queries used.
39 Correct 16 ms 640 KB Correct: 5135 out of 25000 queries used.
40 Correct 15 ms 512 KB Correct: 5168 out of 25000 queries used.
41 Correct 15 ms 512 KB Correct: 5124 out of 25000 queries used.
42 Correct 15 ms 512 KB Correct: 5203 out of 25000 queries used.
43 Correct 20 ms 640 KB Correct: 2087 out of 25000 queries used.
44 Correct 15 ms 512 KB Correct: 5116 out of 25000 queries used.
45 Correct 15 ms 512 KB Correct: 5090 out of 25000 queries used.
46 Correct 15 ms 640 KB Correct: 5068 out of 25000 queries used.
47 Correct 15 ms 512 KB Correct: 5179 out of 25000 queries used.
48 Correct 15 ms 640 KB Correct: 5135 out of 25000 queries used.
49 Correct 17 ms 512 KB Correct: 5091 out of 25000 queries used.
50 Correct 15 ms 512 KB Correct: 5105 out of 25000 queries used.
51 Correct 16 ms 512 KB Correct: 5099 out of 25000 queries used.
52 Correct 15 ms 512 KB Correct: 5128 out of 25000 queries used.
53 Correct 16 ms 640 KB Correct: 5144 out of 25000 queries used.
54 Correct 18 ms 512 KB Correct: 2333 out of 25000 queries used.
55 Correct 15 ms 512 KB Correct: 5196 out of 25000 queries used.
56 Correct 15 ms 512 KB Correct: 5141 out of 25000 queries used.
57 Correct 15 ms 512 KB Correct: 5125 out of 25000 queries used.
58 Correct 15 ms 512 KB Correct: 5115 out of 25000 queries used.
59 Correct 15 ms 512 KB Correct: 5104 out of 25000 queries used.
60 Correct 15 ms 512 KB Correct: 3041 out of 25000 queries used.
61 Correct 17 ms 512 KB Correct: 3317 out of 25000 queries used.
62 Correct 15 ms 512 KB Correct: 2917 out of 25000 queries used.
63 Correct 17 ms 512 KB Correct: 3317 out of 25000 queries used.
64 Correct 15 ms 512 KB Correct: 3103 out of 25000 queries used.
65 Correct 21 ms 544 KB Correct: 2067 out of 25000 queries used.
66 Correct 16 ms 512 KB Correct: 3228 out of 25000 queries used.
67 Correct 18 ms 512 KB Correct: 2018 out of 25000 queries used.
68 Correct 18 ms 640 KB Correct: 2394 out of 25000 queries used.
69 Correct 19 ms 512 KB Correct: 2451 out of 25000 queries used.
70 Correct 18 ms 512 KB Correct: 2414 out of 25000 queries used.