oj.uz

Submission #146994

# Submission time Handle Problem Language Result Execution time Memory
146994 2019-08-27T03:39:37 Z gs14004 City Mapping (NOI18_citymapping) C++17
70.01 / 100
 35 ms 8568 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 1005;

lint mem[MAXN][MAXN];

lint dist(int x, int y){
	if(x == y) return 0;
	if(mem[x][y]) return mem[x][y];
	return mem[x][y] = mem[y][x] = get_distance(x, y);
}

vector<pi> gph[MAXN];
lint dep[MAXN];
bool vis[MAXN];
vector<int> dfn;
int sz[MAXN], msz[MAXN];

void dfs(int x, int p){
	sz[x] = 1;
	msz[x] = 0;
	for(auto &i : gph[x]){
		if(!vis[i.second] && i.second != p){
			dfs(i.second, x);
			sz[x] += sz[i.second];
			msz[x] = max(msz[x], sz[i.second]);
		}
	}
	dfn.push_back(x);
}

int get_center(int v){
	dfn.clear();
	dfs(v, -1);
	pi ret(1e9, -1);
	for(auto &i : dfn){
		pi ans = pi(max(sz(dfn) - sz[i], msz[i]), i);
		ret = min(ret, ans);
	}
	return ret.second;
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	auto make_edge = [&](int s, int e, int x){
//		printf("make_edge(%d, %d, %d)\n", s, e, x);
		gph[s].emplace_back(x, e);
		gph[e].emplace_back(x, s);
		for(int i=0; i<N-1; i++){
			if(!W[i]){
				tie(A[i], B[i], W[i]) = make_tuple(s, e, x);
				break;
			}
		}
	};
	int fp = 1;
	for(int i=1; i<=N; i++){
		if(dist(1, i) < dist(1, fp)) fp = i;
	}
	vector<pi> v;
	for(int i=1; i<=N; i++){
		if(i == fp) continue;
		dep[i] = dist(fp, i);
		v.emplace_back(dep[i], i);
	}
	sort(v.begin(), v.end());
	vector<int> prv = {fp};
	for(auto &i : v){
		if(sz(prv) == 1){
			make_edge(fp, i.second, i.first);
			prv.push_back(i.second);
			continue;
		}
		memset(vis, 0, sizeof(vis));
		int cur_check = 1;
		pi lowest(dep[fp], fp);
		while(!vis[cur_check]){
			int c = get_center(cur_check);
			vis[c] = 1;
			if(dep[c] + dist(c, i.second) == i.first){
				lowest = max(lowest, pi(dep[c], c));
				vector<int> sons;
				for(auto &j : gph[c]){
					if(dep[j.second] > dep[c]){
						sons.push_back(j.second);
					}
				}
				if(sons.empty()) break;
				cur_check = sons.back();
				for(int j=0; j<sz(sons)-1; j++){
					if(dep[sons[j]] + dist(sons[j], i.second) == i.first){
						cur_check = sons[j];
					}
				}
			}
			else{
				for(auto &j : gph[c]){
					if(dep[j.second] < dep[c]){
						cur_check = j.second;
						break;
					}
				}
			}
		}
		make_edge(lowest.second, i.second, dist(lowest.second, i.second));
		prv.push_back(i.second);
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8568 KB Correct: 9454 out of 500000 queries used.
2 Correct 33 ms 8568 KB Correct: 15370 out of 500000 queries used.
3 Correct 27 ms 8440 KB Correct: 11025 out of 500000 queries used.
4 Correct 27 ms 8440 KB Correct: 11021 out of 500000 queries used.
5 Correct 31 ms 8568 KB Correct: 10425 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8568 KB Correct: 9454 out of 500000 queries used.
2 Correct 33 ms 8568 KB Correct: 15370 out of 500000 queries used.
3 Correct 27 ms 8440 KB Correct: 11025 out of 500000 queries used.
4 Correct 27 ms 8440 KB Correct: 11021 out of 500000 queries used.
5 Correct 31 ms 8568 KB Correct: 10425 out of 500000 queries used.
6 Correct 32 ms 8440 KB Correct: 9408 out of 500000 queries used.
7 Correct 32 ms 8440 KB Correct: 11324 out of 500000 queries used.
8 Correct 29 ms 8440 KB Correct: 10994 out of 500000 queries used.
9 Correct 26 ms 8440 KB Correct: 10305 out of 500000 queries used.
10 Correct 30 ms 8440 KB Correct: 10673 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8440 KB Correct: 9336 out of 12000 queries used.
2 Correct 32 ms 8440 KB Correct: 9355 out of 12000 queries used.
3 Correct 32 ms 8440 KB Correct: 9468 out of 12000 queries used.
4 Correct 32 ms 8440 KB Correct: 9349 out of 12000 queries used.
5 Correct 33 ms 8440 KB Correct: 9361 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8440 KB Correct: 9336 out of 12000 queries used.
2 Correct 32 ms 8440 KB Correct: 9355 out of 12000 queries used.
3 Correct 32 ms 8440 KB Correct: 9468 out of 12000 queries used.
4 Correct 32 ms 8440 KB Correct: 9349 out of 12000 queries used.
5 Correct 33 ms 8440 KB Correct: 9361 out of 12000 queries used.
6 Correct 35 ms 8440 KB Correct: 9416 out of 12000 queries used.
7 Correct 34 ms 8492 KB Correct: 9395 out of 12000 queries used.
8 Correct 33 ms 8568 KB Correct: 9439 out of 12000 queries used.
9 Correct 33 ms 8484 KB Correct: 9425 out of 12000 queries used.
10 Correct 32 ms 8440 KB Correct: 9352 out of 12000 queries used.

Subtask #5
13.01 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8568 KB Correct: 9454 out of 500000 queries used.
2 Correct 33 ms 8568 KB Correct: 15370 out of 500000 queries used.
3 Correct 27 ms 8440 KB Correct: 11025 out of 500000 queries used.
4 Correct 27 ms 8440 KB Correct: 11021 out of 500000 queries used.
5 Correct 31 ms 8568 KB Correct: 10425 out of 500000 queries used.
6 Correct 32 ms 8440 KB Correct: 9408 out of 500000 queries used.
7 Correct 32 ms 8440 KB Correct: 11324 out of 500000 queries used.
8 Correct 29 ms 8440 KB Correct: 10994 out of 500000 queries used.
9 Correct 26 ms 8440 KB Correct: 10305 out of 500000 queries used.
10 Correct 30 ms 8440 KB Correct: 10673 out of 500000 queries used.
11 Correct 31 ms 8440 KB Correct: 9336 out of 12000 queries used.
12 Correct 32 ms 8440 KB Correct: 9355 out of 12000 queries used.
13 Correct 32 ms 8440 KB Correct: 9468 out of 12000 queries used.
14 Correct 32 ms 8440 KB Correct: 9349 out of 12000 queries used.
15 Correct 33 ms 8440 KB Correct: 9361 out of 12000 queries used.
16 Correct 35 ms 8440 KB Correct: 9416 out of 12000 queries used.
17 Correct 34 ms 8492 KB Correct: 9395 out of 12000 queries used.
18 Correct 33 ms 8568 KB Correct: 9439 out of 12000 queries used.
19 Correct 33 ms 8484 KB Correct: 9425 out of 12000 queries used.
20 Correct 32 ms 8440 KB Correct: 9352 out of 12000 queries used.
21 Correct 32 ms 8412 KB Correct: 9407 out of 25000 queries used.
22 Correct 32 ms 8440 KB Correct: 11443 out of 25000 queries used.
23 Correct 31 ms 8568 KB Correct: 11070 out of 25000 queries used.
24 Correct 31 ms 8440 KB Correct: 10182 out of 25000 queries used.
25 Correct 28 ms 8440 KB Correct: 11179 out of 25000 queries used.
26 Correct 29 ms 8384 KB Correct: 10982 out of 25000 queries used.
27 Correct 27 ms 8440 KB Correct: 11033 out of 25000 queries used.
28 Correct 28 ms 8444 KB Correct: 10862 out of 25000 queries used.
29 Correct 28 ms 8496 KB Correct: 10755 out of 25000 queries used.
30 Correct 27 ms 8440 KB Correct: 10752 out of 25000 queries used.
31 Correct 27 ms 8440 KB Correct: 10442 out of 25000 queries used.
32 Correct 32 ms 8440 KB Correct: 9365 out of 25000 queries used.
33 Correct 26 ms 8440 KB Correct: 10236 out of 25000 queries used.
34 Correct 26 ms 8440 KB Correct: 10451 out of 25000 queries used.
35 Correct 27 ms 8440 KB Correct: 10413 out of 25000 queries used.
36 Correct 29 ms 8440 KB Correct: 10412 out of 25000 queries used.
37 Correct 28 ms 8440 KB Correct: 10425 out of 25000 queries used.
38 Correct 27 ms 8440 KB Correct: 10282 out of 25000 queries used.
39 Correct 32 ms 8440 KB Correct: 10320 out of 25000 queries used.
40 Correct 26 ms 8440 KB Correct: 10367 out of 25000 queries used.
41 Correct 27 ms 8440 KB Correct: 10268 out of 25000 queries used.
42 Correct 26 ms 8440 KB Correct: 10348 out of 25000 queries used.
43 Correct 32 ms 8440 KB Correct: 9422 out of 25000 queries used.
44 Correct 26 ms 8440 KB Correct: 10228 out of 25000 queries used.
45 Correct 27 ms 8440 KB Correct: 10312 out of 25000 queries used.
46 Correct 26 ms 8440 KB Correct: 10233 out of 25000 queries used.
47 Correct 27 ms 8440 KB Correct: 10423 out of 25000 queries used.
48 Correct 26 ms 8440 KB Correct: 10320 out of 25000 queries used.
49 Correct 27 ms 8444 KB Correct: 10407 out of 25000 queries used.
50 Correct 27 ms 8444 KB Correct: 10364 out of 25000 queries used.
51 Correct 26 ms 8440 KB Correct: 10313 out of 25000 queries used.
52 Correct 27 ms 8412 KB Correct: 10363 out of 25000 queries used.
53 Correct 27 ms 8440 KB Correct: 10453 out of 25000 queries used.
54 Correct 32 ms 8440 KB Correct: 10881 out of 25000 queries used.
55 Correct 27 ms 8440 KB Correct: 10280 out of 25000 queries used.
56 Correct 27 ms 8440 KB Correct: 10270 out of 25000 queries used.
57 Correct 27 ms 8440 KB Correct: 10386 out of 25000 queries used.
58 Correct 26 ms 8432 KB Correct: 10328 out of 25000 queries used.
59 Correct 26 ms 8440 KB Correct: 10304 out of 25000 queries used.
60 Correct 30 ms 8424 KB Correct: 10483 out of 25000 queries used.
61 Correct 30 ms 8380 KB Correct: 10328 out of 25000 queries used.
62 Correct 31 ms 8440 KB Correct: 10360 out of 25000 queries used.
63 Correct 31 ms 8440 KB Correct: 10399 out of 25000 queries used.
64 Correct 31 ms 8412 KB Correct: 10448 out of 25000 queries used.
65 Correct 32 ms 8440 KB Correct: 10030 out of 25000 queries used.
66 Correct 31 ms 8404 KB Correct: 10687 out of 25000 queries used.
67 Correct 31 ms 8444 KB Correct: 11448 out of 25000 queries used.
68 Correct 31 ms 8440 KB Correct: 10540 out of 25000 queries used.
69 Correct 32 ms 8440 KB Correct: 10864 out of 25000 queries used.
70 Correct 32 ms 8440 KB Correct: 10668 out of 25000 queries used.