| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 667977 |
2022-12-02T13:08:48 Z |
Lobo |
Prize (CEOI22_prize) |
C++17 |
|
3500 ms |
401012 KB |
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e6+10;
const int LOG = 20;
int n, k, q, t;
int pp1[maxn][LOG+1], pp2[maxn][LOG+1], tin1[maxn], tin2[maxn], withtin1[maxn], withtin2[maxn], h1[maxn], h2[maxn];
int timer1, timer2, dist1[maxn], dist2[maxn], r1, r2, p1[maxn], p2[maxn];
vector<int> g1[maxn], g2[maxn];
vector<pair<int,pair<int,int>>> g1d[maxn];
void dfstin1(int u) {
for(int i = 1; i <= LOG; i++) {
pp1[u][i] = pp1[pp1[u][i-1]][i-1];
}
tin1[u] = ++timer1;
withtin1[tin1[u]] = u;
for(auto v : g1[u]) {
pp1[v][0] = u;
h1[v] = h1[u]+1;
dfstin1(v);
}
}
int lca1(int u, int v) {
if(h1[u] < h1[v]) swap(u,v);
for(int i = LOG; i >= 0; i--) {
if(h1[pp1[u][i]] >= h1[v]) {
u = pp1[u][i];
}
}
if(u == v) return u;
for(int i = LOG; i >= 0; i--) {
if(pp1[u][i] != pp1[v][i]) {
u = pp1[u][i];
v = pp1[v][i];
}
}
return pp1[u][0];
}
void dfstin2(int u) {
for(int i = 1; i <= LOG; i++) {
pp2[u][i] = pp2[pp2[u][i-1]][i-1];
}
tin2[u] = ++timer2;
withtin2[tin2[u]] = u;
for(auto v : g2[u]) {
h2[v] = h2[u]+1;
pp2[v][0] = u;
dfstin2(v);
}
}
int lca2(int u, int v) {
if(h2[u] < h2[v]) swap(u,v);
for(int i = LOG; i >= 0; i--) {
if(h2[pp2[u][i]] >= h2[v]) {
u = pp2[u][i];
}
}
if(u == v) return u;
for(int i = LOG; i >= 0; i--) {
if(pp2[u][i] != pp2[v][i]) {
u = pp2[u][i];
v = pp2[v][i];
}
}
return pp2[u][0];
}
void dfsd1(int u, int ant) {
assert(g1d[u].size() == 1 || g1d[u].size() == 2);
int v = -1;
int d1u, d1v;
for(auto V : g1d[u]) if(V.fr != ant) {
v = V.fr;
d1u = V.sc.fr;
d1v = V.sc.sc;
int l1 = lca1(u,v);
dist1[l1] = dist1[u]-d1u;
dist1[v] = dist1[l1]+d1v;
dfsd1(v,u);
}
}
void solve() {
cin >> n >> k >> q >> t;
for(int i = 1; i <= n; i++) {
cin >> p1[i];
if(p1[i] == -1) {
r1 = i;
}
else {
g1[p1[i]].pb(i);
}
}
for(int i = 1; i <= n; i++) {
cin >> p2[i];
if(p2[i] == -1) {
r2 = i;
}
else {
g2[p2[i]].pb(i);
}
}
pp1[r1][0] = r1; dfstin1(r1);
pp2[r2][0] = r2; dfstin2(r2);
vector<pair<int,int>> vrt;
for(int i = 1; i <= k; i++) {
vrt.pb(mp(tin2[withtin1[i]],withtin1[i]));
}
if(tin1[r2] > k) {
vrt.pop_back();
vrt.pb(mp(tin2[r2],r2));
}
sort(all(vrt));
for(auto x : vrt) {
cout << x.sc << " ";
}cout << endl;
cout.flush();
vector<pair<int,int>> asks;
for(int i = 0; i+1 < vrt.size(); i++) {
int u = vrt[i].sc;
int v = vrt[i+1].sc;
cout << "? " << u << " " << v << endl;
asks.pb(mp(u,v));
}
cout << "!" << endl;
cout.flush();
dist1[r2] = 0;
dist2[r2] = 0;
for(int i = 0; i < asks.size(); i++) {
int u = asks[i].fr;
int v = asks[i].sc;
int l1 = lca1(u,v);
int l2 = lca2(u,v);
int d1u, d1v, d2u, d2v;
cin >> d1u >> d1v >> d2u >> d2v;
dist2[l2] = dist2[u]-d2u;
dist2[v] = dist2[l2]+d2v;
dist1[l1] = dist1[u]-d1u;
dist1[v] = dist1[l1]+d1v;
// g1d[u].pb(mp(v,mp(d1u,d1v)));
// g1d[v].pb(mp(u,mp(d1v,d1u)));
}
// dist1[r1] = 0;
// dfsd1(r1,-1);
vector<pair<long long,long long>> ans;
for(int i = 1; i <= t; i++) {
int u,v; cin >> u >> v;
assert(dist1[u] != -1);
assert(dist1[v] != -1);
ans.pb(mp((long long) dist1[u]+dist1[v]-2*dist1[lca1(u,v)],(long long) dist2[u]+dist2[v]-2*dist2[lca2(u,v)]));
}
for(int i = 1; i <= t; i++) {
cout << ans[i-1].fr << " " << ans[i-1].sc << endl;
}
cout.flush();
}
int32_t main() {
// ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:145:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int i = 0; i+1 < vrt.size(); i++) {
| ~~~~^~~~~~~~~~~~
Main.cpp:156: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]
156 | for(int i = 0; i < asks.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1688 ms |
238500 KB |
Output is correct |
| 2 |
Correct |
1677 ms |
238716 KB |
Output is correct |
| 3 |
Correct |
1186 ms |
192084 KB |
Output is correct |
| 4 |
Correct |
1202 ms |
191984 KB |
Output is correct |
| 5 |
Correct |
1181 ms |
192252 KB |
Output is correct |
| 6 |
Correct |
1626 ms |
202300 KB |
Output is correct |
| 7 |
Correct |
1597 ms |
202068 KB |
Output is correct |
| 8 |
Correct |
1540 ms |
201944 KB |
Output is correct |
| 9 |
Correct |
1161 ms |
192032 KB |
Output is correct |
| 10 |
Correct |
1193 ms |
192316 KB |
Output is correct |
| 11 |
Correct |
1142 ms |
191800 KB |
Output is correct |
| 12 |
Correct |
1184 ms |
192296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1977 ms |
238704 KB |
Output is correct |
| 2 |
Correct |
2021 ms |
238136 KB |
Output is correct |
| 3 |
Runtime error |
1429 ms |
384976 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1321 ms |
233784 KB |
Output is correct |
| 2 |
Correct |
1408 ms |
233712 KB |
Output is correct |
| 3 |
Correct |
1014 ms |
187644 KB |
Output is correct |
| 4 |
Correct |
1025 ms |
187584 KB |
Output is correct |
| 5 |
Correct |
997 ms |
187632 KB |
Output is correct |
| 6 |
Correct |
1273 ms |
197484 KB |
Output is correct |
| 7 |
Correct |
1270 ms |
197556 KB |
Output is correct |
| 8 |
Correct |
1217 ms |
197588 KB |
Output is correct |
| 9 |
Correct |
1289 ms |
195500 KB |
Output is correct |
| 10 |
Correct |
1052 ms |
195388 KB |
Output is correct |
| 11 |
Correct |
1119 ms |
195480 KB |
Output is correct |
| 12 |
Correct |
1087 ms |
195420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3373 ms |
398840 KB |
Output is correct |
| 2 |
Correct |
3356 ms |
399024 KB |
Output is correct |
| 3 |
Correct |
2158 ms |
306948 KB |
Output is correct |
| 4 |
Correct |
2161 ms |
306680 KB |
Output is correct |
| 5 |
Correct |
2176 ms |
306696 KB |
Output is correct |
| 6 |
Correct |
2590 ms |
326512 KB |
Output is correct |
| 7 |
Correct |
2960 ms |
326740 KB |
Output is correct |
| 8 |
Correct |
2850 ms |
326588 KB |
Output is correct |
| 9 |
Correct |
2731 ms |
322452 KB |
Output is correct |
| 10 |
Correct |
2906 ms |
322492 KB |
Output is correct |
| 11 |
Execution timed out |
3603 ms |
322348 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3578 ms |
401012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
