| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 789210 |
2023-07-21T07:48:27 Z |
ymm |
Prize (CEOI22_prize) |
C++17 |
|
1589 ms |
521884 KB |
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
struct tree {
int n;
int rt;
vector<vector<int>> A;
vector<int> pos, ord;
static int constexpr lg = 22;
vector<int> rmq[lg];
void dfs(int v, int &t) {
pos[v] = ord.size();
ord.push_back(v);
for (int u : A[v]) {
dfs(u, t);
ord.push_back(v);
}
}
int mn(int v, int u) const { return pos[v] < pos[u]? v: u; }
void rmqmake() {
rmq[0] = ord;
int n = ord.size();
Loop (i,0,lg-1) {
rmq[i+1].resize(ord.size());
for (int j = 0; j+(2<<i) <= n; ++j)
rmq[i+1][j] = mn(rmq[i][j], rmq[i][j+(1<<i)]);
}
}
int lca(int v, int u) const {
v = pos[v];
u = pos[u];
if (v > u)
swap(v, u);
int len = u-v+1;
int k = __lg(len);
return mn(rmq[k][v], rmq[k][u+1-(1<<k)]);
}
void init0(int sz) {
n = sz;
A.clear();
A.resize(n);
}
void init1() {
pos.resize(n);
ord.clear();
int dard = 0;
dfs(rt, dard);
rmqmake();
}
};
void read_tree(tree &t) {
Loop (i,0,t.n) {
int p;
scanf("%d", &p);
--p;
if (p < 0)
t.rt = i;
else
t.A[p].push_back(i);
}
t.init1();
}
vector<int> dis_from_root(const tree &t, const vector<int> &ord, const vector<pii> &res)
{
int p = 0;
while (ord[p] != t.rt)
++p;
vector<int> ans(t.n);
int dis = 0;
Loop (i,p,ord.size()-1) {
dis -= res[i].first;
dis += res[i].second;
ans[ord[i+1]] = dis;
}
dis = 0;
LoopR (i,0,p) {
dis -= res[i].second;
dis += res[i].first;
ans[ord[i]] = dis;
}
return ans;
}
int get_dis(const tree &t, const vector<int> &dis, int v, int u)
{
int l = t.lca(v, u);
return -2*dis[l] + dis[v] + dis[u];
}
int main()
{
tree T1, T2;
int n, k, q, t;
scanf("%d%d%d%d", &n, &k, &q, &t);
T1.init0(n);
T2.init0(n);
read_tree(T1);
read_tree(T2);
set<int> myset = {T1.rt, T2.rt};
for (int i = 0; myset.size() < k; ++i)
myset.insert(i);
vector<int> ord(myset.begin(), myset.end());
for (int x : myset)
printf("%d ", x+1);
printf("\n");
Loop (i,0,k-1)
printf("? %d %d\n", ord[i]+1, ord[i+1]+1);
printf("!\n");
fflush(stdout);
vector<pii> res1, res2;
Loop (i,0,k-1) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
res1.push_back({a, b});
res2.push_back({c, d});
}
vector<int> dis1, dis2;
dis1 = dis_from_root(T1, ord, res1);
dis2 = dis_from_root(T2, ord, res2);
vector<pii> ans;
while (t--) {
int v, u;
scanf("%d%d", &v, &u);
--v; --u;
int x = get_dis(T1, dis1, v, u);
int y = get_dis(T2, dis2, v, u);
ans.push_back({x, y});
}
for (auto [x, y] : ans)
printf("%d %d\n", x, y);
fflush(stdout);
}
Compilation message
Main.cpp: In function 'std::vector<int> dis_from_root(const tree&, const std::vector<int>&, const std::vector<std::pair<int, int> >&)':
Main.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
| ^
Main.cpp:82:2: note: in expansion of macro 'Loop'
82 | Loop (i,p,ord.size()-1) {
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:113:31: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
113 | for (int i = 0; myset.size() < k; ++i)
| ~~~~~~~~~~~~~^~~
Main.cpp: In function 'void read_tree(tree&)':
Main.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d", &p);
| ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d%d%d%d", &n, &k, &q, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | scanf("%d%d%d%d", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d%d", &v, &u);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
740 ms |
263188 KB |
Output is correct |
| 2 |
Correct |
741 ms |
265308 KB |
Output is correct |
| 3 |
Runtime error |
520 ms |
234624 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
752 ms |
265160 KB |
Output is correct |
| 2 |
Correct |
727 ms |
262352 KB |
Output is correct |
| 3 |
Runtime error |
505 ms |
234636 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
660 ms |
257832 KB |
Output is correct |
| 2 |
Correct |
627 ms |
257852 KB |
Output is correct |
| 3 |
Runtime error |
438 ms |
228884 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1586 ms |
515572 KB |
Output is correct |
| 2 |
Correct |
1480 ms |
515652 KB |
Output is correct |
| 3 |
Runtime error |
1074 ms |
457488 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1589 ms |
521884 KB |
Output is correct |
| 2 |
Correct |
1585 ms |
521572 KB |
Output is correct |
| 3 |
Runtime error |
1134 ms |
461688 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
