oj.uz

Submission #961741

# Submission time Handle Problem Language Result Execution time Memory
961741 2024-04-12T11:47:24 Z vjudge1 City Mapping (NOI18_citymapping) C++17
63.91 / 100
 3 ms 1176 KB 
#include "citymapping.h"
#include <bits/stdc++.h>

namespace operators
{
	template <typename T1, typename T2>
	std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
	{
		in >> x.first >> x.second;
		return in;
	}

	template <typename T1, typename T2>
	std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
	{
		out << x.first << " " << x.second;
		return out;
	}

	template <typename T1>
	std::istream &operator>>(std::istream &in, std::vector<T1> &x)
	{
		for (auto &i : x)
			in >> i;
		return in;
	}

	template <typename T1>
	std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
	{
		for (auto &i : x)
			out << i << " ";
		return out;
	}

	template <typename T1>
	std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
	{
		for (auto &i : x)
			out << i << " ";
		return out;
	}

	template <typename T1>
	std::ostream &operator<<(std::ostream &out, std::multiset<T1> &x)
	{
		for (auto &i : x)
			out << i << " ";
		return out;
	}
}

// name spaces
using namespace std;
using namespace operators;
// end of name spaces

// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines

vector<pair<pll, ll>> edges;
vector<ll> D;

void solve(vector<ll> &v, ll PREV)
{
	if (v.empty())
		return;
	ll frth = v[0];
	for (ll el : v)
		if (D[frth] < D[el])
			frth = el;
	vector<pll> bf;
	ll last = frth;
	for (ll el : v)
		if (el != frth)
			bf.pb({get_distance(frth + 1, el + 1), el});
	sort(all(bf));
	vector<vector<ll>> toSolve;
	vector<pii> dists;
	for (auto [curd, el] : bf)
	{
		if (curd + D[el] == D[frth])
		{
			edges.pb({{last, el}, D[last] - D[el]});
			last = el;
			toSolve.pb({});
			dists.pb({curd, el});
		}
		else
		{
			int d1 = D[el] - D[PREV];
			int d2 = curd;
			int bf = ((D[el] + curd) - D[frth]) / 2;
			int dToV = curd - bf;
			for (int i = 0; i < dists.size(); ++i)
				if (dToV == dists[i].f)
					toSolve[i].pb(el);
		}
	}
	for (int i = 0; i < dists.size(); ++i)
		solve(toSolve[i], dists[i].s);
	edges.pb({{PREV, last}, D[last] - D[PREV]});
}

void find_roads(int N, int Q, int A[], int B[], int W[])
{
	D.resize(N);
	pll mx = {0, 0};
	for (ll i = 1; i < N; ++i)
		mx = max(mx, mp((ll)get_distance(1, i + 1), i));
	for (ll i = 0; i < N; ++i)
		D[i] = (ll)get_distance(mx.s + 1, i + 1);
	vector<ll> vtc;
	for (ll i = 0; i < N; ++i)
		if (i != mx.s)
			vtc.pb(i);
	solve(vtc, mx.s);

	ll i = 0;
	for (auto [e, v] : edges)
	{
		// cout << A[i] << " " << B[i] << " " << W[i] << "!\n";
		A[i] = e.f + 1;
		B[i] = e.s + 1;
		W[i] = abs(v);
		++i;
	}
	return;
}

// ////////////////////////////////////////////////////////

// #include "citymapping.h"
// #include <bits/stdc++.h>
// using namespace std;

// static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
// static long long dist[1005];
// static vector<pair<int, int>> adjlist[1005];
// static vector<pair<pair<int, int>, int>> edgelist, user_edgelist;

// static void dfs(int x, int p, long long d, int dep)
// {
// 	dist[x] = d;
// 	depth[x] = dep;
// 	twok[x][0] = p;
// 	for (int i = 1; i <= 10; i++)
// 	{
// 		if (twok[x][i - 1] == -1)
// 			break;
// 		twok[x][i] = twok[twok[x][i - 1]][i - 1];
// 	}
// 	for (int i = 0; i < (int)adjlist[x].size(); i++)
// 	{
// 		if (adjlist[x][i].first == p)
// 			continue;
// 		dfs(adjlist[x][i].first, x, d + adjlist[x][i].second, dep + 1);
// 	}
// }

// static int lca(int x, int y)
// {
// 	if (depth[x] > depth[y])
// 		swap(x, y);
// 	int dd = depth[y] - depth[x];
// 	for (int i = 0; i <= 10; i++)
// 		if (dd & (1 << i))
// 			y = twok[y][i];
// 	if (x == y)
// 		return x;
// 	for (int i = 10; i >= 0; i--)
// 	{
// 		if (twok[x][i] != twok[y][i])
// 		{
// 			x = twok[x][i];
// 			y = twok[y][i];
// 		}
// 	}
// 	return twok[x][0];
// }

// long long get_distance(int X, int Y)
// {
// 	if (X <= 0 || X > N || Y <= 0 || Y > N)
// 	{
// 		printf("Wrong Answer: get_distance() arguments out of range.\n");
// 		exit(0);
// 	}
// 	curQ++;
// 	if (curQ > Q)
// 	{
// 		printf("Wrong Answer: Too many calls to get_distance().\n");
// 		exit(0);
// 	}
// 	return dist[X - 1] + dist[Y - 1] - dist[lca(X - 1, Y - 1)] * 2;
// }

// int main()
// {
// 	if (scanf("%d%d%d", &N, &Q, &S) != 3)
// 	{
// 		printf("Wrong Input Format\n");
// 		exit(0);
// 	}
// 	for (int i = 0; i < N - 1; i++)
// 	{
// 		int a, b, w;
// 		if (scanf("%d%d%d", &a, &b, &w) != 3)
// 		{
// 			printf("Wrong Input Format\n");
// 			return 0;
// 		}
// 		a--;
// 		b--;
// 		adjlist[a].push_back(make_pair(b, w));
// 		adjlist[b].push_back(make_pair(a, w));
// 		edgelist.push_back(make_pair(make_pair(min(a, b) + 1, max(a, b) + 1), w));
// 	}
// 	sort(edgelist.begin(), edgelist.end());
// 	memset(twok, -1, sizeof(twok));
// 	dfs(0, -1, 0, 0);
// 	int A[N - 1], B[N - 1], W[N - 1];
// 	memset(A, 0, sizeof(A));
// 	memset(B, 0, sizeof(B));
// 	memset(W, 0, sizeof(W));
// 	find_roads(N, Q, A, B, W);
// 	for (int i = 0; i < N - 1; i++)
// 	{
// 		user_edgelist.push_back(make_pair(make_pair(min(A[i], B[i]), max(A[i], B[i])), W[i]));
// 	}
// 	sort(user_edgelist.begin(), user_edgelist.end());
// 	if (edgelist != user_edgelist)
// 	{
// 		printf("Wrong Answer: Reported list of edges differ from actual.\n");
// 		exit(0);
// 	}
// 	cout << "Correct";
// 	exit(0);
// 	if (S <= 4)
// 	{
// 		printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q);
// 		exit(0);
// 	}
// 	else
// 	{
// 		if (curQ <= target)
// 			printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q);
// 		else if (curQ >= 12000)
// 			printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (10.0 - 10.0 * ((double)(curQ - 12000) / 13000)) / 43 * 100, curQ, Q);
// 		else
// 			printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (40.0 - 30.0 * ((double)(curQ - target) / (12000 - target))) / 43 * 100, curQ, Q);
// 	}
// }

Compilation message

citymapping.cpp: In function 'void solve(std::vector<long long int>&, long long int)':
citymapping.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for (int i = 0; i < dists.size(); ++i)
      |                    ~~^~~~~~~~~~~~~~
citymapping.cpp:101:8: warning: unused variable 'd1' [-Wunused-variable]
  101 |    int d1 = D[el] - D[PREV];
      |        ^~
citymapping.cpp:102:8: warning: unused variable 'd2' [-Wunused-variable]
  102 |    int d2 = curd;
      |        ^~
citymapping.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  for (int i = 0; i < dists.size(); ++i)
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct: 2994 out of 500000 queries used.
2 Correct 2 ms 604 KB Correct: 2997 out of 500000 queries used.
3 Correct 2 ms 604 KB Correct: 5153 out of 500000 queries used.
4 Correct 1 ms 604 KB Correct: 5966 out of 500000 queries used.
5 Correct 2 ms 1176 KB Correct: 11585 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct: 2994 out of 500000 queries used.
2 Correct 2 ms 604 KB Correct: 2997 out of 500000 queries used.
3 Correct 2 ms 604 KB Correct: 5153 out of 500000 queries used.
4 Correct 1 ms 604 KB Correct: 5966 out of 500000 queries used.
5 Correct 2 ms 1176 KB Correct: 11585 out of 500000 queries used.
6 Correct 1 ms 604 KB Correct: 2985 out of 500000 queries used.
7 Correct 2 ms 860 KB Correct: 15557 out of 500000 queries used.
8 Correct 2 ms 476 KB Correct: 5217 out of 500000 queries used.
9 Correct 2 ms 472 KB Correct: 6173 out of 500000 queries used.
10 Correct 2 ms 604 KB Correct: 5610 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct: 2970 out of 12000 queries used.
2 Correct 2 ms 604 KB Correct: 2976 out of 12000 queries used.
3 Correct 2 ms 604 KB Correct: 2997 out of 12000 queries used.
4 Correct 1 ms 604 KB Correct: 2976 out of 12000 queries used.
5 Correct 1 ms 600 KB Correct: 2970 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct: 2970 out of 12000 queries used.
2 Correct 2 ms 604 KB Correct: 2976 out of 12000 queries used.
3 Correct 2 ms 604 KB Correct: 2997 out of 12000 queries used.
4 Correct 1 ms 604 KB Correct: 2976 out of 12000 queries used.
5 Correct 1 ms 600 KB Correct: 2970 out of 12000 queries used.
6 Correct 1 ms 604 KB Correct: 2991 out of 12000 queries used.
7 Correct 1 ms 604 KB Correct: 2985 out of 12000 queries used.
8 Correct 1 ms 604 KB Correct: 2997 out of 12000 queries used.
9 Correct 1 ms 604 KB Correct: 2988 out of 12000 queries used.
10 Correct 1 ms 604 KB Correct: 2979 out of 12000 queries used.

Subtask #5
6.91 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct: 2994 out of 500000 queries used.
2 Correct 2 ms 604 KB Correct: 2997 out of 500000 queries used.
3 Correct 2 ms 604 KB Correct: 5153 out of 500000 queries used.
4 Correct 1 ms 604 KB Correct: 5966 out of 500000 queries used.
5 Correct 2 ms 1176 KB Correct: 11585 out of 500000 queries used.
6 Correct 1 ms 604 KB Correct: 2985 out of 500000 queries used.
7 Correct 2 ms 860 KB Correct: 15557 out of 500000 queries used.
8 Correct 2 ms 476 KB Correct: 5217 out of 500000 queries used.
9 Correct 2 ms 472 KB Correct: 6173 out of 500000 queries used.
10 Correct 2 ms 604 KB Correct: 5610 out of 500000 queries used.
11 Correct 1 ms 604 KB Correct: 2970 out of 12000 queries used.
12 Correct 2 ms 604 KB Correct: 2976 out of 12000 queries used.
13 Correct 2 ms 604 KB Correct: 2997 out of 12000 queries used.
14 Correct 1 ms 604 KB Correct: 2976 out of 12000 queries used.
15 Correct 1 ms 600 KB Correct: 2970 out of 12000 queries used.
16 Correct 1 ms 604 KB Correct: 2991 out of 12000 queries used.
17 Correct 1 ms 604 KB Correct: 2985 out of 12000 queries used.
18 Correct 1 ms 604 KB Correct: 2997 out of 12000 queries used.
19 Correct 1 ms 604 KB Correct: 2988 out of 12000 queries used.
20 Correct 1 ms 604 KB Correct: 2979 out of 12000 queries used.
21 Correct 1 ms 600 KB Correct: 2985 out of 25000 queries used.
22 Correct 2 ms 604 KB Correct: 5375 out of 25000 queries used.
23 Correct 2 ms 472 KB Correct: 3023 out of 25000 queries used.
24 Correct 2 ms 604 KB Correct: 4329 out of 25000 queries used.
25 Correct 2 ms 604 KB Correct: 5263 out of 25000 queries used.
26 Correct 1 ms 604 KB Correct: 5011 out of 25000 queries used.
27 Correct 2 ms 528 KB Correct: 5158 out of 25000 queries used.
28 Correct 2 ms 604 KB Correct: 5280 out of 25000 queries used.
29 Correct 2 ms 604 KB Correct: 5545 out of 25000 queries used.
30 Correct 2 ms 604 KB Correct: 5753 out of 25000 queries used.
31 Correct 1 ms 524 KB Correct: 5963 out of 25000 queries used.
32 Correct 1 ms 604 KB Correct: 2982 out of 25000 queries used.
33 Correct 1 ms 604 KB Correct: 5931 out of 25000 queries used.
34 Correct 2 ms 860 KB Correct: 5963 out of 25000 queries used.
35 Correct 1 ms 604 KB Correct: 5943 out of 25000 queries used.
36 Correct 2 ms 476 KB Correct: 5921 out of 25000 queries used.
37 Correct 2 ms 672 KB Correct: 5935 out of 25000 queries used.
38 Correct 1 ms 604 KB Correct: 5966 out of 25000 queries used.
39 Correct 1 ms 600 KB Correct: 5938 out of 25000 queries used.
40 Correct 1 ms 472 KB Correct: 5946 out of 25000 queries used.
41 Correct 2 ms 472 KB Correct: 5944 out of 25000 queries used.
42 Correct 2 ms 604 KB Correct: 5954 out of 25000 queries used.
43 Correct 1 ms 604 KB Correct: 2991 out of 25000 queries used.
44 Correct 1 ms 604 KB Correct: 5882 out of 25000 queries used.
45 Correct 1 ms 604 KB Correct: 5913 out of 25000 queries used.
46 Correct 1 ms 604 KB Correct: 5881 out of 25000 queries used.
47 Correct 1 ms 604 KB Correct: 5939 out of 25000 queries used.
48 Correct 2 ms 604 KB Correct: 5971 out of 25000 queries used.
49 Correct 1 ms 604 KB Correct: 5970 out of 25000 queries used.
50 Correct 2 ms 604 KB Correct: 5955 out of 25000 queries used.
51 Correct 2 ms 604 KB Correct: 5971 out of 25000 queries used.
52 Correct 2 ms 604 KB Correct: 5938 out of 25000 queries used.
53 Correct 1 ms 604 KB Correct: 6227 out of 25000 queries used.
54 Correct 2 ms 860 KB Correct: 15519 out of 25000 queries used.
55 Correct 1 ms 604 KB Correct: 5958 out of 25000 queries used.
56 Correct 1 ms 604 KB Correct: 5940 out of 25000 queries used.
57 Correct 1 ms 604 KB Correct: 6228 out of 25000 queries used.
58 Correct 2 ms 604 KB Correct: 5889 out of 25000 queries used.
59 Correct 1 ms 604 KB Correct: 5921 out of 25000 queries used.
60 Correct 2 ms 604 KB Correct: 6814 out of 25000 queries used.
61 Correct 2 ms 600 KB Correct: 6743 out of 25000 queries used.
62 Correct 1 ms 604 KB Correct: 5977 out of 25000 queries used.
63 Correct 2 ms 604 KB Correct: 6032 out of 25000 queries used.
64 Correct 2 ms 604 KB Correct: 6008 out of 25000 queries used.
65 Correct 2 ms 860 KB Correct: 7418 out of 25000 queries used.
66 Correct 2 ms 604 KB Correct: 6599 out of 25000 queries used.
67 Correct 1 ms 604 KB Correct: 3194 out of 25000 queries used.
68 Correct 3 ms 1084 KB Correct: 16019 out of 25000 queries used.
69 Correct 2 ms 860 KB Correct: 10882 out of 25000 queries used.
70 Correct 2 ms 860 KB Correct: 11891 out of 25000 queries used.