| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 667702 |
2022-12-01T21:34:30 Z |
Lobo |
Prize (CEOI22_prize) |
C++17 |
|
747 ms |
336 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 = 5e5+10;
int n, k, q, t;
// int pp1[maxn][11], pp2[maxn][11], 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 <= 20; 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 = 20; i >= 0; i--) {
// if(h1[pp1[u][i]] >= h1[v]) {
// u = pp1[u][i];
// }
// }
// if(u == v) return u;
// for(int i = 20; 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 <= 20; 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 = 20; i >= 0; i--) {
// if(h2[pp2[u][i]] >= h2[v]) {
// u = pp2[u][i];
// }
// }
// if(u == v) return u;
// for(int i = 20; 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) {
// 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;
// }
// if(v == -1) return;
// 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++) {
int wtf; cin >> wtf;
// cin >> p1[i];
// if(p1[i] == -1) {
// r1 = i;
// }
// else {
// g1[p1[i]].pb(i);
// }
}
for(int i = 1; i <= n; i++) {
int wtf; cin >> wtf;
// 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[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;
for(int i = 1; i <= k; i++) {
cout << i << " ";
}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));
// }
for(int i = 1; i <= k-1; i++) {
cout << "? " << i << " " << i+1 << endl;
}
cout << "!" << endl;
cout.flush();
for(int i = 1; i <= k-1; i++) {
int x; cin >> x >> x >> x >> x;
}
// dist2[r2] = 0;
// for(int i = 0; i < asks.size(); i++) {
// int u = asks[i].fr;
// int v = asks[i].sc;
// 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;
// g1d[u].pb(mp(v,mp(d1u,d1v)));
// g1d[v].pb(mp(u,mp(d1v,d1u)));
// }
// dfsd1(r1,-1);
for(int i = 1; i <= t; i++) {
int u,v; cin >> u >> v;
// cout << dist1[u]+dist1[v]-2*dist1[lca1(u,v)] << " " << dist2[u]+dist2[v]-2*dist2[lca2(u,v)] << endl;
cout << 1 << " " << 1 << 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
386 ms |
336 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
509 ms |
276 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
298 ms |
272 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
567 ms |
268 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
747 ms |
284 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
