oj.uz

Submission #91617

# Submission time Handle Problem Language Result Execution time Memory
91617 2018-12-28T16:52:56 Z model_code City Mapping (NOI18_citymapping) C++17
100 / 100
 20 ms 916 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;

int curQ;
map< pair<int, int>, long long > memo;

long long my_query(int x, int y) {
	if (x == y) return 0;
	if (x > y) swap(x, y);
	if (memo.find(make_pair(x, y)) == memo.end()) {
		curQ++;
		return memo[make_pair(x, y)] = get_distance(x+1, y+1);
	}
	else return memo[make_pair(x, y)];
}

int weight[1005];
vector< pair<int, int> > child[1005];
vector< pair<long long, int> > V;
vector<int> blocked;
bool block[1005];

int dfs(int x, int p) {
	int ans = 1;
	for (int i = 0; i < child[x].size(); i++) if (!block[child[x][i].first]) ans += dfs(child[x][i].first, x);
	return weight[x] = ans;
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	int myrt = 0;
	for (int i = 0; i < N; i++) {
		if (i != myrt) V.push_back(make_pair(my_query(myrt, i), i));
	}
	sort(V.begin(), V.end());
	
	for (int i = 0; i < V.size(); i++) {
		int newnode = V[i].second;
		long long dist = V[i].first;
		int rt = myrt;
		//printf("joining node %d\n",newnode);
		while (1) {
			vector< pair<int, long long> > V2;
			long long curd = 0;
			dfs(rt, -1);
			//printf("%d\n", rt);
			if (weight[rt] == 1) {
				A[i] = newnode + 1;
				B[i] = rt + 1;
				W[i] = my_query(myrt, newnode) - my_query(myrt, rt);
				//printf("%d %d\n", rt, newnode);
				child[rt].push_back(make_pair(newnode, W[i]));
				for (int j = 0; j < blocked.size(); j++) block[blocked[j]] = 0;
				blocked.clear();
				break;
			}
			int leaf = rt;
			V2.push_back(make_pair(rt, 0));
			while (child[leaf].size() > 0) {
				int mx = -1, mxnode = myrt;
				for (int i = 0; i < child[leaf].size(); i++) {
					if (block[child[leaf][i].first]) continue;
					if (weight[child[leaf][i].first] > mx) {
						mx = weight[child[leaf][i].first];
						mxnode = i;
					}
				}
				if (mx == -1) break;
				//printf("%d!\n", mxnode);
				curd += child[leaf][mxnode].second;
				leaf = child[leaf][mxnode].first;
				
				V2.push_back(make_pair(leaf, curd));
			}
			long long bc = my_query(leaf, newnode);
			long long ab = my_query(myrt, leaf) - my_query(myrt, rt);
			long long ac = my_query(myrt, newnode) - my_query(myrt, rt);
			long long sum = (bc + ab + ac) / 2;
			long long a = sum - bc, b = sum - ac, c = sum - ab;
			for (int j = 0; j < V2.size(); j++) {
				if (V2[j].second == a) {
					rt = V2[j].first;
					if (j+1 != V2.size()) {
						block[V2[j+1].first] = 1;
						blocked.push_back(V2[j+1].first);
					}
					break;
				}
			}
		}
	}
	
	/* check degrees */
	int degree[N];
	memset(degree, 0, sizeof(degree));
	for (int i = 0; i < N-1; i++) {
		degree[A[i]-1]++;
		degree[B[i]-1]++;
	}
	for (int i = 0; i < N; i++) assert(degree[i] <= 3);
}

Compilation message

citymapping.cpp: In function 'int dfs(int, int)':
citymapping.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < child[x].size(); i++) if (!block[child[x][i].first]) ans += dfs(child[x][i].first, x);
                  ~~^~~~~~~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~
citymapping.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < blocked.size(); j++) block[blocked[j]] = 0;
                     ~~^~~~~~~~~~~~~~~~
citymapping.cpp:61:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < child[leaf].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~~
citymapping.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < V2.size(); j++) {
                    ~~^~~~~~~~~~~
citymapping.cpp:83:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (j+1 != V2.size()) {
          ~~~~^~~~~~~~~~~~
citymapping.cpp:79:28: warning: unused variable 'b' [-Wunused-variable]
    long long a = sum - bc, b = sum - ac, c = sum - ab;
                            ^
citymapping.cpp:79:42: warning: unused variable 'c' [-Wunused-variable]
    long long a = sum - bc, b = sum - ac, c = sum - ab;
                                          ^
citymapping.cpp:39:13: warning: unused variable 'dist' [-Wunused-variable]
   long long dist = V[i].first;
             ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 732 KB Correct: 2691 out of 500000 queries used.
2 Correct 13 ms 760 KB Correct: 2421 out of 500000 queries used.
3 Correct 12 ms 856 KB Correct: 4517 out of 500000 queries used.
4 Correct 13 ms 888 KB Correct: 5567 out of 500000 queries used.
5 Correct 14 ms 760 KB Correct: 3387 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 732 KB Correct: 2691 out of 500000 queries used.
2 Correct 13 ms 760 KB Correct: 2421 out of 500000 queries used.
3 Correct 12 ms 856 KB Correct: 4517 out of 500000 queries used.
4 Correct 13 ms 888 KB Correct: 5567 out of 500000 queries used.
5 Correct 14 ms 760 KB Correct: 3387 out of 500000 queries used.
6 Correct 16 ms 760 KB Correct: 2009 out of 500000 queries used.
7 Correct 13 ms 632 KB Correct: 2063 out of 500000 queries used.
8 Correct 12 ms 820 KB Correct: 4244 out of 500000 queries used.
9 Correct 13 ms 888 KB Correct: 5089 out of 500000 queries used.
10 Correct 13 ms 712 KB Correct: 3054 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 760 KB Correct: 2086 out of 12000 queries used.
2 Correct 16 ms 760 KB Correct: 2304 out of 12000 queries used.
3 Correct 16 ms 732 KB Correct: 2457 out of 12000 queries used.
4 Correct 17 ms 736 KB Correct: 2470 out of 12000 queries used.
5 Correct 16 ms 760 KB Correct: 2240 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 760 KB Correct: 2086 out of 12000 queries used.
2 Correct 16 ms 760 KB Correct: 2304 out of 12000 queries used.
3 Correct 16 ms 732 KB Correct: 2457 out of 12000 queries used.
4 Correct 17 ms 736 KB Correct: 2470 out of 12000 queries used.
5 Correct 16 ms 760 KB Correct: 2240 out of 12000 queries used.
6 Correct 18 ms 760 KB Correct: 2473 out of 12000 queries used.
7 Correct 16 ms 724 KB Correct: 2382 out of 12000 queries used.
8 Correct 15 ms 732 KB Correct: 2207 out of 12000 queries used.
9 Correct 15 ms 732 KB Correct: 2235 out of 12000 queries used.
10 Correct 16 ms 760 KB Correct: 2302 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 732 KB Correct: 2691 out of 500000 queries used.
2 Correct 13 ms 760 KB Correct: 2421 out of 500000 queries used.
3 Correct 12 ms 856 KB Correct: 4517 out of 500000 queries used.
4 Correct 13 ms 888 KB Correct: 5567 out of 500000 queries used.
5 Correct 14 ms 760 KB Correct: 3387 out of 500000 queries used.
6 Correct 16 ms 760 KB Correct: 2009 out of 500000 queries used.
7 Correct 13 ms 632 KB Correct: 2063 out of 500000 queries used.
8 Correct 12 ms 820 KB Correct: 4244 out of 500000 queries used.
9 Correct 13 ms 888 KB Correct: 5089 out of 500000 queries used.
10 Correct 13 ms 712 KB Correct: 3054 out of 500000 queries used.
11 Correct 15 ms 760 KB Correct: 2086 out of 12000 queries used.
12 Correct 16 ms 760 KB Correct: 2304 out of 12000 queries used.
13 Correct 16 ms 732 KB Correct: 2457 out of 12000 queries used.
14 Correct 17 ms 736 KB Correct: 2470 out of 12000 queries used.
15 Correct 16 ms 760 KB Correct: 2240 out of 12000 queries used.
16 Correct 18 ms 760 KB Correct: 2473 out of 12000 queries used.
17 Correct 16 ms 724 KB Correct: 2382 out of 12000 queries used.
18 Correct 15 ms 732 KB Correct: 2207 out of 12000 queries used.
19 Correct 15 ms 732 KB Correct: 2235 out of 12000 queries used.
20 Correct 16 ms 760 KB Correct: 2302 out of 12000 queries used.
21 Correct 18 ms 760 KB Correct: 2502 out of 25000 queries used.
22 Correct 13 ms 760 KB Correct: 2071 out of 25000 queries used.
23 Correct 13 ms 764 KB Correct: 2284 out of 25000 queries used.
24 Correct 14 ms 632 KB Correct: 2036 out of 25000 queries used.
25 Correct 12 ms 760 KB Correct: 4436 out of 25000 queries used.
26 Correct 12 ms 796 KB Correct: 4358 out of 25000 queries used.
27 Correct 12 ms 888 KB Correct: 4307 out of 25000 queries used.
28 Correct 12 ms 888 KB Correct: 4417 out of 25000 queries used.
29 Correct 13 ms 888 KB Correct: 4502 out of 25000 queries used.
30 Correct 12 ms 888 KB Correct: 4442 out of 25000 queries used.
31 Correct 13 ms 888 KB Correct: 5151 out of 25000 queries used.
32 Correct 16 ms 760 KB Correct: 2223 out of 25000 queries used.
33 Correct 13 ms 836 KB Correct: 5083 out of 25000 queries used.
34 Correct 13 ms 812 KB Correct: 5158 out of 25000 queries used.
35 Correct 13 ms 888 KB Correct: 5100 out of 25000 queries used.
36 Correct 12 ms 860 KB Correct: 5118 out of 25000 queries used.
37 Correct 13 ms 888 KB Correct: 5144 out of 25000 queries used.
38 Correct 13 ms 860 KB Correct: 5102 out of 25000 queries used.
39 Correct 13 ms 888 KB Correct: 5135 out of 25000 queries used.
40 Correct 13 ms 888 KB Correct: 5168 out of 25000 queries used.
41 Correct 13 ms 888 KB Correct: 5124 out of 25000 queries used.
42 Correct 13 ms 888 KB Correct: 5203 out of 25000 queries used.
43 Correct 18 ms 760 KB Correct: 2087 out of 25000 queries used.
44 Correct 13 ms 888 KB Correct: 5116 out of 25000 queries used.
45 Correct 13 ms 808 KB Correct: 5090 out of 25000 queries used.
46 Correct 12 ms 888 KB Correct: 5068 out of 25000 queries used.
47 Correct 13 ms 888 KB Correct: 5179 out of 25000 queries used.
48 Correct 13 ms 888 KB Correct: 5135 out of 25000 queries used.
49 Correct 13 ms 888 KB Correct: 5091 out of 25000 queries used.
50 Correct 13 ms 864 KB Correct: 5105 out of 25000 queries used.
51 Correct 13 ms 860 KB Correct: 5099 out of 25000 queries used.
52 Correct 13 ms 888 KB Correct: 5128 out of 25000 queries used.
53 Correct 12 ms 908 KB Correct: 5144 out of 25000 queries used.
54 Correct 14 ms 760 KB Correct: 2333 out of 25000 queries used.
55 Correct 13 ms 916 KB Correct: 5196 out of 25000 queries used.
56 Correct 13 ms 888 KB Correct: 5141 out of 25000 queries used.
57 Correct 13 ms 888 KB Correct: 5125 out of 25000 queries used.
58 Correct 13 ms 888 KB Correct: 5115 out of 25000 queries used.
59 Correct 13 ms 888 KB Correct: 5104 out of 25000 queries used.
60 Correct 13 ms 748 KB Correct: 3041 out of 25000 queries used.
61 Correct 14 ms 760 KB Correct: 3317 out of 25000 queries used.
62 Correct 12 ms 760 KB Correct: 2917 out of 25000 queries used.
63 Correct 13 ms 752 KB Correct: 3317 out of 25000 queries used.
64 Correct 12 ms 764 KB Correct: 3103 out of 25000 queries used.
65 Correct 13 ms 680 KB Correct: 2067 out of 25000 queries used.
66 Correct 13 ms 760 KB Correct: 3228 out of 25000 queries used.
67 Correct 13 ms 632 KB Correct: 2018 out of 25000 queries used.
68 Correct 15 ms 632 KB Correct: 2394 out of 25000 queries used.
69 Correct 14 ms 732 KB Correct: 2451 out of 25000 queries used.
70 Correct 14 ms 760 KB Correct: 2414 out of 25000 queries used.