#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<vector<int>> tree;
vector<pair<pll, ll>> edges;
vector<ll> D, sz;
void dfs(int v)
{
sz[v] = 1;
for (auto tov : tree[v])
{
dfs(tov);
sz[v] += sz[tov];
}
}
void find_roads(int N, int Q, int A[], int B[], int W[])
{
tree.resize(N);
D.resize(N);
sz.resize(N);
vector<pii> target;
for (ll i = 1; i < N; ++i)
{
D[i] = (ll)get_distance(1, i + 1);
target.pb({D[i], i});
sort(all(target));
}
ll i = 0;
vector<ll> pr(N);
for (auto [d, v] : target)
{
vector<ll> used(N, 0);
dfs(0);
ll root = 0;
used[root] = 1;
while (true)
{
ll bf = root;
while (true)
{
ll to = -1;
for (auto tov : tree[root])
if (!used[tov] and (to == -1 or sz[to] < sz[tov]))
to = tov;
if (to == -1)
break;
root = to;
used[root] = 1;
}
if (root == bf)
{
tree[root].pb(v);
A[i] = v + 1;
B[i] = root + 1;
W[i] = D[v] - D[root];
pr[v] = root;
++i;
break;
}
ll D1 = get_distance(root + 1, v + 1);
ll upTo = D1 - ((D1 + D[v] - D[root]) / 2);
if (D[v] == D[root] + D1)
continue;
while (upTo > 0 and root)
{
upTo -= D[root] - D[pr[root]];
if (upTo >= 0)
root = pr[root];
}
}
}
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);
// }
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
604 KB |
Correct: 2691 out of 500000 queries used. |
| 2 |
Correct |
20 ms |
604 KB |
Correct: 2421 out of 500000 queries used. |
| 3 |
Correct |
21 ms |
624 KB |
Correct: 4517 out of 500000 queries used. |
| 4 |
Correct |
24 ms |
620 KB |
Correct: 5567 out of 500000 queries used. |
| 5 |
Correct |
26 ms |
608 KB |
Correct: 3387 out of 500000 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
604 KB |
Correct: 2691 out of 500000 queries used. |
| 2 |
Correct |
20 ms |
604 KB |
Correct: 2421 out of 500000 queries used. |
| 3 |
Correct |
21 ms |
624 KB |
Correct: 4517 out of 500000 queries used. |
| 4 |
Correct |
24 ms |
620 KB |
Correct: 5567 out of 500000 queries used. |
| 5 |
Correct |
26 ms |
608 KB |
Correct: 3387 out of 500000 queries used. |
| 6 |
Incorrect |
18 ms |
680 KB |
Reported list of edges differ from actual. |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
604 KB |
Correct: 2086 out of 12000 queries used. |
| 2 |
Correct |
20 ms |
668 KB |
Correct: 2304 out of 12000 queries used. |
| 3 |
Correct |
21 ms |
600 KB |
Correct: 2457 out of 12000 queries used. |
| 4 |
Correct |
21 ms |
640 KB |
Correct: 2470 out of 12000 queries used. |
| 5 |
Correct |
23 ms |
668 KB |
Correct: 2240 out of 12000 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
604 KB |
Correct: 2086 out of 12000 queries used. |
| 2 |
Correct |
20 ms |
668 KB |
Correct: 2304 out of 12000 queries used. |
| 3 |
Correct |
21 ms |
600 KB |
Correct: 2457 out of 12000 queries used. |
| 4 |
Correct |
21 ms |
640 KB |
Correct: 2470 out of 12000 queries used. |
| 5 |
Correct |
23 ms |
668 KB |
Correct: 2240 out of 12000 queries used. |
| 6 |
Incorrect |
16 ms |
600 KB |
Reported list of edges differ from actual. |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
604 KB |
Correct: 2691 out of 500000 queries used. |
| 2 |
Correct |
20 ms |
604 KB |
Correct: 2421 out of 500000 queries used. |
| 3 |
Correct |
21 ms |
624 KB |
Correct: 4517 out of 500000 queries used. |
| 4 |
Correct |
24 ms |
620 KB |
Correct: 5567 out of 500000 queries used. |
| 5 |
Correct |
26 ms |
608 KB |
Correct: 3387 out of 500000 queries used. |
| 6 |
Incorrect |
18 ms |
680 KB |
Reported list of edges differ from actual. |
| 7 |
Halted |
0 ms |
0 KB |
- |
