oj.uz

Submission #698408

# Submission time Handle Problem Language Result Execution time Memory
698408 2023-02-13T11:34:55 Z vjudge1 Drawing (CEOI22_drawing) C++14
100 / 100
 235 ms 45620 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long LL;

const int maxn = 1e6 + 10;
int n;
vector<int> G[maxn];
using Point = pair<int, int>;
pair<Point, int> Ps[maxn];
int Ans[maxn];
LL cross(Point a, Point b, Point c) {
  return (LL)a.X * (b.Y - c.Y) + (LL)b.X * (c.Y - a.Y) + (LL)c.X * (a.Y - b.Y);
}
bool cmp(const pair<Point, int>& a, const pair<Point, int>& b) {
  return cross(Ps[0].X, a.X, b.X) >= 0;
}
void solve(int u, int fa, int& pi) {
  Ans[u] = Ps[pi++].second;
  for (int v : G[u])
    if (v != fa) solve(v, u, pi);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n;
  for (int i = 1, a, b; i < n; i++)
    cin >> a >> b, G[a].push_back(b), G[b].push_back(a);
  for (int i = 0, x, y; i < n; i++) cin >> x >> y, Ps[i] = {{x, y}, i + 1};
  sort(Ps, Ps + n);
  sort(Ps + 1, Ps + n, cmp);
  int pi = 0;
  solve(1, 0, pi);
  for (int i = 1; i <= n; i++) printf("%d ", Ans[i]);
  printf("\n");
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 33340 KB Output is correct
2 Correct 108 ms 35000 KB Output is correct
3 Correct 107 ms 34196 KB Output is correct
4 Correct 122 ms 36240 KB Output is correct
5 Correct 102 ms 35332 KB Output is correct
6 Correct 101 ms 33264 KB Output is correct
7 Correct 108 ms 33612 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24100 KB Output is correct
2 Correct 15 ms 24096 KB Output is correct
3 Correct 14 ms 24148 KB Output is correct
4 Correct 15 ms 24148 KB Output is correct
5 Correct 16 ms 24148 KB Output is correct
6 Correct 15 ms 24096 KB Output is correct
7 Correct 16 ms 24088 KB Output is correct
8 Correct 15 ms 24020 KB Output is correct
9 Correct 15 ms 24164 KB Output is correct
10 Correct 15 ms 24084 KB Output is correct
11 Correct 15 ms 24208 KB Output is correct
12 Correct 15 ms 24112 KB Output is correct
13 Correct 14 ms 24084 KB Output is correct
14 Correct 15 ms 24076 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24100 KB Output is correct
2 Correct 15 ms 24096 KB Output is correct
3 Correct 14 ms 24148 KB Output is correct
4 Correct 15 ms 24148 KB Output is correct
5 Correct 16 ms 24148 KB Output is correct
6 Correct 15 ms 24096 KB Output is correct
7 Correct 16 ms 24088 KB Output is correct
8 Correct 15 ms 24020 KB Output is correct
9 Correct 15 ms 24164 KB Output is correct
10 Correct 15 ms 24084 KB Output is correct
11 Correct 15 ms 24208 KB Output is correct
12 Correct 15 ms 24112 KB Output is correct
13 Correct 14 ms 24084 KB Output is correct
14 Correct 15 ms 24076 KB Output is correct
15 Correct 21 ms 24584 KB Output is correct
16 Correct 20 ms 24660 KB Output is correct
17 Correct 20 ms 24660 KB Output is correct
18 Correct 19 ms 24788 KB Output is correct
19 Correct 19 ms 24816 KB Output is correct
20 Correct 19 ms 24588 KB Output is correct
21 Correct 19 ms 24612 KB Output is correct
22 Correct 20 ms 24584 KB Output is correct
23 Correct 20 ms 24660 KB Output is correct
24 Correct 19 ms 24660 KB Output is correct
25 Correct 20 ms 24788 KB Output is correct
26 Correct 19 ms 24764 KB Output is correct
27 Correct 22 ms 24532 KB Output is correct
28 Correct 20 ms 24632 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24100 KB Output is correct
2 Correct 15 ms 24096 KB Output is correct
3 Correct 14 ms 24148 KB Output is correct
4 Correct 15 ms 24148 KB Output is correct
5 Correct 16 ms 24148 KB Output is correct
6 Correct 15 ms 24096 KB Output is correct
7 Correct 16 ms 24088 KB Output is correct
8 Correct 15 ms 24020 KB Output is correct
9 Correct 15 ms 24164 KB Output is correct
10 Correct 15 ms 24084 KB Output is correct
11 Correct 15 ms 24208 KB Output is correct
12 Correct 15 ms 24112 KB Output is correct
13 Correct 14 ms 24084 KB Output is correct
14 Correct 15 ms 24076 KB Output is correct
15 Correct 21 ms 24584 KB Output is correct
16 Correct 20 ms 24660 KB Output is correct
17 Correct 20 ms 24660 KB Output is correct
18 Correct 19 ms 24788 KB Output is correct
19 Correct 19 ms 24816 KB Output is correct
20 Correct 19 ms 24588 KB Output is correct
21 Correct 19 ms 24612 KB Output is correct
22 Correct 20 ms 24584 KB Output is correct
23 Correct 20 ms 24660 KB Output is correct
24 Correct 19 ms 24660 KB Output is correct
25 Correct 20 ms 24788 KB Output is correct
26 Correct 19 ms 24764 KB Output is correct
27 Correct 22 ms 24532 KB Output is correct
28 Correct 20 ms 24632 KB Output is correct
29 Correct 71 ms 30480 KB Output is correct
30 Correct 79 ms 31704 KB Output is correct
31 Correct 76 ms 31252 KB Output is correct
32 Correct 79 ms 31912 KB Output is correct
33 Correct 78 ms 31832 KB Output is correct
34 Correct 77 ms 30496 KB Output is correct
35 Correct 77 ms 30772 KB Output is correct
36 Correct 69 ms 29548 KB Output is correct
37 Correct 84 ms 31308 KB Output is correct
38 Correct 76 ms 31312 KB Output is correct
39 Correct 77 ms 31820 KB Output is correct
40 Correct 76 ms 31068 KB Output is correct
41 Correct 70 ms 29516 KB Output is correct
42 Correct 75 ms 30748 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 33340 KB Output is correct
2 Correct 108 ms 35000 KB Output is correct
3 Correct 107 ms 34196 KB Output is correct
4 Correct 122 ms 36240 KB Output is correct
5 Correct 102 ms 35332 KB Output is correct
6 Correct 101 ms 33264 KB Output is correct
7 Correct 108 ms 33612 KB Output is correct
8 Correct 16 ms 24100 KB Output is correct
9 Correct 15 ms 24096 KB Output is correct
10 Correct 14 ms 24148 KB Output is correct
11 Correct 15 ms 24148 KB Output is correct
12 Correct 16 ms 24148 KB Output is correct
13 Correct 15 ms 24096 KB Output is correct
14 Correct 16 ms 24088 KB Output is correct
15 Correct 15 ms 24020 KB Output is correct
16 Correct 15 ms 24164 KB Output is correct
17 Correct 15 ms 24084 KB Output is correct
18 Correct 15 ms 24208 KB Output is correct
19 Correct 15 ms 24112 KB Output is correct
20 Correct 14 ms 24084 KB Output is correct
21 Correct 15 ms 24076 KB Output is correct
22 Correct 21 ms 24584 KB Output is correct
23 Correct 20 ms 24660 KB Output is correct
24 Correct 20 ms 24660 KB Output is correct
25 Correct 19 ms 24788 KB Output is correct
26 Correct 19 ms 24816 KB Output is correct
27 Correct 19 ms 24588 KB Output is correct
28 Correct 19 ms 24612 KB Output is correct
29 Correct 20 ms 24584 KB Output is correct
30 Correct 20 ms 24660 KB Output is correct
31 Correct 19 ms 24660 KB Output is correct
32 Correct 20 ms 24788 KB Output is correct
33 Correct 19 ms 24764 KB Output is correct
34 Correct 22 ms 24532 KB Output is correct
35 Correct 20 ms 24632 KB Output is correct
36 Correct 71 ms 30480 KB Output is correct
37 Correct 79 ms 31704 KB Output is correct
38 Correct 76 ms 31252 KB Output is correct
39 Correct 79 ms 31912 KB Output is correct
40 Correct 78 ms 31832 KB Output is correct
41 Correct 77 ms 30496 KB Output is correct
42 Correct 77 ms 30772 KB Output is correct
43 Correct 69 ms 29548 KB Output is correct
44 Correct 84 ms 31308 KB Output is correct
45 Correct 76 ms 31312 KB Output is correct
46 Correct 77 ms 31820 KB Output is correct
47 Correct 76 ms 31068 KB Output is correct
48 Correct 70 ms 29516 KB Output is correct
49 Correct 75 ms 30748 KB Output is correct
50 Correct 116 ms 34344 KB Output is correct
51 Correct 211 ms 43652 KB Output is correct
52 Correct 206 ms 42608 KB Output is correct
53 Correct 226 ms 43340 KB Output is correct
54 Correct 235 ms 45620 KB Output is correct
55 Correct 203 ms 40768 KB Output is correct
56 Correct 224 ms 41364 KB Output is correct
57 Correct 45 ms 27352 KB Output is correct
58 Correct 229 ms 42512 KB Output is correct
59 Correct 217 ms 42344 KB Output is correct
60 Correct 225 ms 45324 KB Output is correct
61 Correct 227 ms 42920 KB Output is correct
62 Correct 49 ms 27296 KB Output is correct
63 Correct 218 ms 41328 KB Output is correct