| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 709114 |
2023-03-13T06:29:32 Z |
mansur |
Prize (CEOI22_prize) |
C++17 |
|
609 ms |
221124 KB |
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
#define pf push_front
#define pb push_back
#define vt vector
#define s second
#define f first
#define nl '\n'
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vt<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vt<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
const int N = 2e6, mod = 1e9 + 7;
const ll inf = 1e18;
double eps = 1e-15;
bool flg = 0;
vt<int> g[2][N], is(N);
vt<pii> s, gr[N];
void dfs(int u, int cnt) {
is[u] = 1;
for (int to: g[0][u]) {
if (sz(s) == cnt) return;
s.pb({u, to});
dfs(to, cnt);
}
}
int tin[N], tout[N], timer;
pii up[N][18];
void bld(int u) {
tin[u] = timer++;
for (int i = 1; i < 18; i++) {
up[u][i].f = up[up[u][i - 1].f][i - 1].f;
up[u][i].s = up[u][i - 1].s + up[up[u][i - 1].f][i - 1].s;
}
for (auto [to, w]: gr[u]) {
up[to][0] = {u, w};
bld(to);
}
tout[u] = timer++;
}
bool isp(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (isp(a, b)) return a;
if (isp(b, a)) return b;
for (int i = 17; i >= 0; i--) {
if (isp(up[a][i].f, b)) continue;
a = up[a][i].f;
}
return up[a][0].f;
}
int get(int a, int b) {
if (a == b) return 0;
int res = 0;
for (int i = 17; i >= 0; i--) {
if (isp(up[a][i].f, b)) continue;
res += up[a][i].s;
a = up[a][i].f;
}
return res + up[a][0].s;
}
void slv() {
int n, k, q, t;
cin >> n >> k >> q >> t;
int r1, r2;
for (int i = 1; i <= n; i++) {
int p;
cin >> p;
if (p == -1) r1 = i;
else g[0][p].pb(i);
}
for (int i = 1; i <= n; i++) {
int p;
cin >> p;
if (p == -1) r2 = i;
else g[1][p].pb(i);
}
if (q == k - 1) {
dfs(r1, k - 1);
for (int i = 1; i <= n; i++) {
if (is[i]) cout << i << ' ';
}
cout << endl;
for (int i = 0; i < k - 1; i++) {
cout << "? " << s[i].f << ' ' << s[i].s << endl;
int x;
cin >> x >> x >> x >> x;
gr[s[i].f].pb({s[i].s, x});
}
up[r1][0] = {r1, 0};
bld(r1);
cout << '!' << endl;
while (t--) {
int a, b;
cin >> a >> b;
int lc = lca(a, b);
cout << get(a, lc) + get(b, lc) << nl;
}
}
}
main() {
//freopen("shops.in", "r", stdin);
//freopen("shops.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int tp = 1;
if (flg) cin >> tp;
while (tp--) {
slv();
}
}
Compilation message
Main.cpp: In function 'void slv()':
Main.cpp:91:10: warning: variable 'r2' set but not used [-Wunused-but-set-variable]
91 | int r1, r2;
| ^~
Main.cpp: At global scope:
Main.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
128 | main() {
| ^~~~
Main.cpp: In function 'void slv()':
Main.cpp:117:9: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
117 | bld(r1);
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
289 ms |
187136 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
414 ms |
180312 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
305 ms |
180284 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
533 ms |
211764 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
609 ms |
221124 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
