oj.uz

Submission #147016

# Submission time Handle Problem Language Result Execution time Memory
147016 2019-08-27T06:12:35 Z gs14004 City Mapping (NOI18_citymapping) C++17
100 / 100
 26 ms 8480 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];
int sz[MAXN], msz[MAXN], par[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]);
		}
	}
}
 
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;
			}
		}
	};
	vector<pi> v;
	for(int i=2; i<=N; i++){
		dep[i] = dist(1, i);
		v.emplace_back(dep[i], i);
	}
	sort(v.begin(), v.end());
	vector<int> prv = {1};
	for(auto &i : v){
		if(sz(prv) == 1){
			par[i.second] = 1;
			make_edge(1, i.second, i.first);
			prv.push_back(i.second);
			continue;
		}
		memset(vis, 0, sizeof(vis));
		int curpos = 1;
		pi lowest(0, 1);
		dfs(1, -1);
		while(true){
			int L = curpos;
			while(true){
				pi ans(0, 0);
				for(auto &j : gph[L]){
					if(j.second != par[L]) ans = max(ans, pi(sz[j.second], j.second));
				}
				if(ans.second == 0) break;
				L = ans.second;
			}
			lint d1 = dep[L];
			lint d2 = dist(L, i.second);
			lint d3 = dep[i.second];
			lint branch = (d1 + d2 - d3) / 2;
			int pL = -1;
			bool found_vis = vis[L];
			while(d1 - branch < dep[L]){
				pL = L;
				L = par[L];
				if(vis[L]) found_vis = 1;
			}
			if(found_vis) break;
			vis[L] = 1;
			vector<int> sons;
			for(auto &j : gph[L]){
				if(j.second != par[L] && j.second != pL){
					sons.push_back(j.second);
				}
			}
			lowest = max(lowest, pi(dep[L], L));
			assert(sz(sons) <= 2);
			if(sz(sons) == 0) break;
			if(sz(sons) == 1){
				curpos = sons[0];
			}
			else{
				if(dep[sons[0]] + dist(sons[0], i.second) == dep[i.second]){
					curpos = sons[0];
				}
				else curpos = sons[1];
			}
		}
		make_edge(lowest.second, i.second, dist(lowest.second, i.second));
		par[i.second] = lowest.second;
		prv.push_back(i.second);
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8056 KB Correct: 2680 out of 500000 queries used.
2 Correct 22 ms 8184 KB Correct: 2891 out of 500000 queries used.
3 Correct 21 ms 8316 KB Correct: 4915 out of 500000 queries used.
4 Correct 18 ms 8440 KB Correct: 6057 out of 500000 queries used.
5 Correct 20 ms 8184 KB Correct: 3431 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8056 KB Correct: 2680 out of 500000 queries used.
2 Correct 22 ms 8184 KB Correct: 2891 out of 500000 queries used.
3 Correct 21 ms 8316 KB Correct: 4915 out of 500000 queries used.
4 Correct 18 ms 8440 KB Correct: 6057 out of 500000 queries used.
5 Correct 20 ms 8184 KB Correct: 3431 out of 500000 queries used.
6 Correct 25 ms 7672 KB Correct: 2011 out of 500000 queries used.
7 Correct 22 ms 7928 KB Correct: 2561 out of 500000 queries used.
8 Correct 19 ms 8388 KB Correct: 4628 out of 500000 queries used.
9 Correct 19 ms 8444 KB Correct: 5617 out of 500000 queries used.
10 Correct 21 ms 8056 KB Correct: 3078 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7544 KB Correct: 2083 out of 12000 queries used.
2 Correct 24 ms 7808 KB Correct: 2320 out of 12000 queries used.
3 Correct 24 ms 7932 KB Correct: 2483 out of 12000 queries used.
4 Correct 24 ms 7928 KB Correct: 2445 out of 12000 queries used.
5 Correct 23 ms 7672 KB Correct: 2235 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7544 KB Correct: 2083 out of 12000 queries used.
2 Correct 24 ms 7808 KB Correct: 2320 out of 12000 queries used.
3 Correct 24 ms 7932 KB Correct: 2483 out of 12000 queries used.
4 Correct 24 ms 7928 KB Correct: 2445 out of 12000 queries used.
5 Correct 23 ms 7672 KB Correct: 2235 out of 12000 queries used.
6 Correct 25 ms 7900 KB Correct: 2473 out of 12000 queries used.
7 Correct 24 ms 7800 KB Correct: 2382 out of 12000 queries used.
8 Correct 23 ms 7644 KB Correct: 2207 out of 12000 queries used.
9 Correct 23 ms 7800 KB Correct: 2235 out of 12000 queries used.
10 Correct 24 ms 7800 KB Correct: 2302 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8056 KB Correct: 2680 out of 500000 queries used.
2 Correct 22 ms 8184 KB Correct: 2891 out of 500000 queries used.
3 Correct 21 ms 8316 KB Correct: 4915 out of 500000 queries used.
4 Correct 18 ms 8440 KB Correct: 6057 out of 500000 queries used.
5 Correct 20 ms 8184 KB Correct: 3431 out of 500000 queries used.
6 Correct 25 ms 7672 KB Correct: 2011 out of 500000 queries used.
7 Correct 22 ms 7928 KB Correct: 2561 out of 500000 queries used.
8 Correct 19 ms 8388 KB Correct: 4628 out of 500000 queries used.
9 Correct 19 ms 8444 KB Correct: 5617 out of 500000 queries used.
10 Correct 21 ms 8056 KB Correct: 3078 out of 500000 queries used.
11 Correct 24 ms 7544 KB Correct: 2083 out of 12000 queries used.
12 Correct 24 ms 7808 KB Correct: 2320 out of 12000 queries used.
13 Correct 24 ms 7932 KB Correct: 2483 out of 12000 queries used.
14 Correct 24 ms 7928 KB Correct: 2445 out of 12000 queries used.
15 Correct 23 ms 7672 KB Correct: 2235 out of 12000 queries used.
16 Correct 25 ms 7900 KB Correct: 2473 out of 12000 queries used.
17 Correct 24 ms 7800 KB Correct: 2382 out of 12000 queries used.
18 Correct 23 ms 7644 KB Correct: 2207 out of 12000 queries used.
19 Correct 23 ms 7800 KB Correct: 2235 out of 12000 queries used.
20 Correct 24 ms 7800 KB Correct: 2302 out of 12000 queries used.
21 Correct 24 ms 7924 KB Correct: 2502 out of 25000 queries used.
22 Correct 22 ms 7928 KB Correct: 2605 out of 25000 queries used.
23 Correct 21 ms 7900 KB Correct: 2931 out of 25000 queries used.
24 Correct 23 ms 7928 KB Correct: 2559 out of 25000 queries used.
25 Correct 18 ms 8312 KB Correct: 4887 out of 25000 queries used.
26 Correct 19 ms 8184 KB Correct: 4734 out of 25000 queries used.
27 Correct 22 ms 8284 KB Correct: 4668 out of 25000 queries used.
28 Correct 18 ms 8312 KB Correct: 4788 out of 25000 queries used.
29 Correct 19 ms 8284 KB Correct: 4861 out of 25000 queries used.
30 Correct 19 ms 8312 KB Correct: 4782 out of 25000 queries used.
31 Correct 21 ms 8440 KB Correct: 5664 out of 25000 queries used.
32 Correct 23 ms 7672 KB Correct: 2223 out of 25000 queries used.
33 Correct 18 ms 8312 KB Correct: 5593 out of 25000 queries used.
34 Correct 21 ms 8480 KB Correct: 5689 out of 25000 queries used.
35 Correct 19 ms 8312 KB Correct: 5615 out of 25000 queries used.
36 Correct 18 ms 8312 KB Correct: 5642 out of 25000 queries used.
37 Correct 18 ms 8312 KB Correct: 5651 out of 25000 queries used.
38 Correct 18 ms 8440 KB Correct: 5610 out of 25000 queries used.
39 Correct 18 ms 8312 KB Correct: 5664 out of 25000 queries used.
40 Correct 18 ms 8440 KB Correct: 5684 out of 25000 queries used.
41 Correct 19 ms 8440 KB Correct: 5649 out of 25000 queries used.
42 Correct 20 ms 8440 KB Correct: 5709 out of 25000 queries used.
43 Correct 24 ms 7672 KB Correct: 2087 out of 25000 queries used.
44 Correct 18 ms 8312 KB Correct: 5625 out of 25000 queries used.
45 Correct 18 ms 8312 KB Correct: 5586 out of 25000 queries used.
46 Correct 18 ms 8312 KB Correct: 5578 out of 25000 queries used.
47 Correct 18 ms 8312 KB Correct: 5678 out of 25000 queries used.
48 Correct 18 ms 8312 KB Correct: 5641 out of 25000 queries used.
49 Correct 18 ms 8312 KB Correct: 5613 out of 25000 queries used.
50 Correct 20 ms 8312 KB Correct: 5631 out of 25000 queries used.
51 Correct 20 ms 8312 KB Correct: 5639 out of 25000 queries used.
52 Correct 18 ms 8440 KB Correct: 5648 out of 25000 queries used.
53 Correct 18 ms 8440 KB Correct: 5698 out of 25000 queries used.
54 Correct 22 ms 8056 KB Correct: 2989 out of 25000 queries used.
55 Correct 18 ms 8312 KB Correct: 5711 out of 25000 queries used.
56 Correct 18 ms 8312 KB Correct: 5661 out of 25000 queries used.
57 Correct 20 ms 8312 KB Correct: 5642 out of 25000 queries used.
58 Correct 19 ms 8312 KB Correct: 5618 out of 25000 queries used.
59 Correct 18 ms 8312 KB Correct: 5630 out of 25000 queries used.
60 Correct 20 ms 7928 KB Correct: 3074 out of 25000 queries used.
61 Correct 20 ms 8156 KB Correct: 3343 out of 25000 queries used.
62 Correct 20 ms 7928 KB Correct: 2943 out of 25000 queries used.
63 Correct 20 ms 7928 KB Correct: 3351 out of 25000 queries used.
64 Correct 20 ms 7928 KB Correct: 3136 out of 25000 queries used.
65 Correct 23 ms 7672 KB Correct: 2598 out of 25000 queries used.
66 Correct 20 ms 8056 KB Correct: 3232 out of 25000 queries used.
67 Correct 22 ms 7672 KB Correct: 2522 out of 25000 queries used.
68 Correct 21 ms 7672 KB Correct: 3088 out of 25000 queries used.
69 Correct 22 ms 7800 KB Correct: 2952 out of 25000 queries used.
70 Correct 22 ms 8184 KB Correct: 2911 out of 25000 queries used.