| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 791632 |
2023-07-24T08:23:08 Z |
ono_de206 |
Prize (CEOI22_prize) |
C++14 |
|
0 ms |
0 KB |
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
// #define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
out << c.first << ' ' << c.second;
return out;
}
template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
const int sz = v.size();
for (int i = 0; i < sz; i++) {
if (i) out << ' ';
out << v[i];
}
return out;
}
template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
for (T &x : v) in >> x;
return in;
}
template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}
const int mxn = 1010;
pair<int , int> P[2][mxn];
int dis[2][mxn][mxn], lca[2][mxn][mxn];
struct tree {
int n, lg, cnt;
vector<int> dep;
vector<vector<int>> jump, g;
bool did;
tree(int _n) : n(_n) {
dep.resize(n + 1);
adj.resize(n + 1);
did = 0;
lg = cnt = 0;
while((1 << lg) < n) lg++;
jump.resize(n + 1, vector<int>(lg));
}
void build(int to = 1, fr = 0) {
dep[to] = dep[fr] + 1;
jump[to][0] = fr;
for(int x : g[to]) {
if(x == fr) continue;
build(x, to);
}
}
void add(int x, int y) {
g[x].pb(y);
g[y].pb(x);
cnt++;
if(cnt == n - 1) build();
}
void buildLCA() {
if(did) return;
did = 1;
for(int j = 1; j < lg; j++) {
for(int i = 1; i <= n; i++) {
jump[i][j] = jump[jump[i][j - 1]][j - 1];
}
}
}
int lca(int x, int y) {
buildLCA();
if(dep[x] < dep[y]) swap(x, y);
int dff = dep[x] - dep[y];
for(int i = 0; i < lg; i++) {
if((dff >> i) & 1) x = jump[x][i];
}
if(x == y) return x;
for(int i = lg - 1; i >= 0; i--) {
if(jump[x][i] != jump[y][i]) {
x = jump[x][i];
y = jump[y][i];
}
}
return jump[x][0];
}
bool isOn(int x, int y, int z) {
int p = lca(x, y);
if(dep[p] > dep[z]) return 0;
return (lca(x, z) == z || lca(y, z) == z);
}
};
void go() {
int n, k, q, t;
tree t1(n), t2(n);
for(int i = 1, x; i <= n; i++) {
cin >> x;
if(x != -1) t1.add(x, i);
}
for(int i = 1, x; i <= n; i++) {
cin >> x;
if(x != -1) t2.add(x, i);
}
for(int i = 1; i <= k; i++) {
cout << i << " \n"[i == k];
}
cout.flush();
for(int i = 1; i < k; i++) {
cout << "? " << i << ' ' << i + 1 << '\n';
}
cout << "!\n";
cout.flush();
for(int i = 2; i <= k; i++) {
cin >> P[0][i].ff >> P[0][i].ss >> P[1][i].ff >> P[1][i].ss;
}
for(int i = 1; i <= k; i++) {
for(int j = i; j <= k; j++) {
lca[0][i][j] = t1.lca(i, j);
lca[1][i][j] = t2.lca(i, j);
}
}
for(int i = 1; i <= k; i++) {
for(int p = 0; p < 2; p++) {
pair<int, int> dp{0, 0};
int ls = i;
for(int j = i + 1; j <= k; j++) {
if(lca[p][i][j] == lca[p][ls][j]) dp = {P[p][j].ff - dp.ss + dp.ff, P[p][j].ss};
else if(lca[p][i][j] == lca[p][i][ls]) dp.ss = P[p][j].ss - P[p][j].ff;
else continue;
ls = j;
dis[p][i][j] = dp.ff + dp.ss;
}
}
}
for(int i = k; i >= 1; i--) {
for(int p = 0; p < 2; p++) {
pair<int, int> dp{0, 0};
int ls = i;
for(int j = i - 1; j >= 1; j--) {
if(lca[p][i][j] == lca[p][ls][j]) dp = {P[p][j].ss - dp.ss + dp.ff, P[p][j + 1].ff};
else if(lca[p][i][j] == lca[p][i][ls]) dp.ss = P[p][j + 1].ff - P[p][j + 1].ss;
else continue;
ls = j;
dis[p][j][i] = dp.ff + dp.ss;
}
}
}
vector<pair<int, int>> Q;
for(int i = 1, x, y; i <= t; i++) {
cin >> x >> y;
if(x > y) swap(x, y);
Q.eb(x, y);
}
for(auto it : Q) {
cout << dis[0][it.ff][it.ss] << ' ' << dis[1][it.ff][it.ss] << '\n';
cout.flush();
}
}
signed main() {
// #ifndef ONO
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
// #endif
// fast;
int t = 1;
// cin >> t;
while(t--) {
go();
}
return 0;
}
Compilation message
Main.cpp:68:25: error: 'fr' has not been declared
68 | void build(int to = 1, fr = 0) {
| ^~
Main.cpp: In constructor 'tree::tree(int)':
Main.cpp:61:3: error: 'adj' was not declared in this scope; did you mean 'add'?
61 | adj.resize(n + 1);
| ^~~
| add
Main.cpp: In member function 'void tree::build(int, int)':
Main.cpp:69:17: error: 'fr' was not declared in this scope; did you mean 'ff'?
69 | dep[to] = dep[fr] + 1;
| ^~
| ff
Main.cpp: In function 'void go()':
Main.cpp:119:12: warning: unused variable 'q' [-Wunused-variable]
119 | int n, k, q, t;
| ^
