oj.uz

Submission #147007

# Submission time Handle Problem Language Result Execution time Memory
147007 2019-08-27T04:51:41 Z gs14004 City Mapping (NOI18_citymapping) C++17
41 / 100
 34 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], 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]);
		}
	}
	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;
			}
		}
	};
	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 cur_check = 1;
		pi lowest(dep[1], 1);
		while(cur_check && !vis[cur_check]){
			int c = get_center(cur_check);
			vis[c] = 1;
			vector<int> sons;
			for(auto &j : gph[c]){
				if(!vis[j.second] && dep[j.second] > dep[c]){
					sons.push_back(j.second);
				}
			}
			if(sons.empty()){
				if(dist(1, c) + dist(c, i.second) == dist(1, i.second)){
					lowest = max(lowest, pi(dep[c], c));
				}
				continue;
			}
			int next_trial = sons[0];
			lint d1 = dep[next_trial];
			lint d2 = dist(next_trial, i.second);
			lint d3 = dep[i.second];
			if(d1 + d2 == d3){
				cur_check = next_trial;
				continue;
			}
			lint branch = (d1 + d2 - d3) / 2;
			if(d1 - branch < dep[c]){
				cur_check = par[c];
			}
			else{
				lowest = max(lowest, pi(dep[c], c));
				if(sz(sons) >= 2){
					cur_check = sons[1];
				}
				if(sz(sons) == 3){
					if(dist(1, sons[2]) + dist(sons[2], i.second) == dist(1, i.second)){
						cur_check = sons[2];
					}
				}
			}
		}
		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 34 ms 8440 KB Correct: 8706 out of 500000 queries used.
2 Correct 32 ms 8440 KB Correct: 9050 out of 500000 queries used.
3 Correct 27 ms 8440 KB Correct: 7364 out of 500000 queries used.
4 Correct 26 ms 8440 KB Correct: 7764 out of 500000 queries used.
5 Correct 31 ms 8440 KB Correct: 7655 out of 500000 queries used.

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8440 KB Correct: 8706 out of 500000 queries used.
2 Correct 32 ms 8440 KB Correct: 9050 out of 500000 queries used.
3 Correct 27 ms 8440 KB Correct: 7364 out of 500000 queries used.
4 Correct 26 ms 8440 KB Correct: 7764 out of 500000 queries used.
5 Correct 31 ms 8440 KB Correct: 7655 out of 500000 queries used.
6 Correct 33 ms 8440 KB Correct: 8689 out of 500000 queries used.
7 Incorrect 32 ms 8484 KB Reported list of edges differ from actual.
8 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8440 KB Correct: 8636 out of 12000 queries used.
2 Correct 32 ms 8416 KB Correct: 8653 out of 12000 queries used.
3 Correct 32 ms 8440 KB Correct: 8737 out of 12000 queries used.
4 Correct 34 ms 8444 KB Correct: 8647 out of 12000 queries used.
5 Correct 32 ms 8440 KB Correct: 8642 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8440 KB Correct: 8636 out of 12000 queries used.
2 Correct 32 ms 8416 KB Correct: 8653 out of 12000 queries used.
3 Correct 32 ms 8440 KB Correct: 8737 out of 12000 queries used.
4 Correct 34 ms 8444 KB Correct: 8647 out of 12000 queries used.
5 Correct 32 ms 8440 KB Correct: 8642 out of 12000 queries used.
6 Correct 32 ms 8444 KB Correct: 8709 out of 12000 queries used.
7 Correct 32 ms 8452 KB Correct: 8679 out of 12000 queries used.
8 Correct 32 ms 8568 KB Correct: 8728 out of 12000 queries used.
9 Correct 32 ms 8440 KB Correct: 8704 out of 12000 queries used.
10 Correct 32 ms 8440 KB Correct: 8667 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8440 KB Correct: 8706 out of 500000 queries used.
2 Correct 32 ms 8440 KB Correct: 9050 out of 500000 queries used.
3 Correct 27 ms 8440 KB Correct: 7364 out of 500000 queries used.
4 Correct 26 ms 8440 KB Correct: 7764 out of 500000 queries used.
5 Correct 31 ms 8440 KB Correct: 7655 out of 500000 queries used.
6 Correct 33 ms 8440 KB Correct: 8689 out of 500000 queries used.
7 Incorrect 32 ms 8484 KB Reported list of edges differ from actual.
8 Halted 0 ms 0 KB -