| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 632112 |
2022-08-19T12:46:34 Z |
arayi |
Prize (CEOI22_prize) |
C++17 |
|
2528 ms |
1048576 KB |
// Arayi
#include <bits/stdc++.h>
#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int>
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;
lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x, ld y1, ld x2, ld y2)
{
return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
return (a * (a + 1LL)) / 2;
}
mt19937 rnd(363542);
char vow[] = {'a', 'e', 'i', 'o', 'u'};
int dx[] = {0, -1, 0, 1, -1, -1, 1, 1, 0};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1, 0};
char dc[] = {'R', 'D', 'L', 'U'};
const int N = 2e6 + 20;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const ld e = 1e-13;
const int T = 200;
lli bp(lli a, lli b = mod - 2LL)
{
lli ret = 1;
while (b)
{
if (b & 1)
ret *= a, ret %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return ret;
}
ostream &operator<<(ostream &c, pir a)
{
c << a.fr << " " << a.sc;
return c;
}
template <class T>
void maxi(T &a, T b)
{
a = max(a, b);
}
template <class T>
void mini(T &a, T b)
{
a = min(a, b);
}
int n, k, q, t;
vii g[2][N], g1[2][N];
int l[2], l1[2], pr[2][N][20], xr[2][N];
int s[2][N];
bool cl[N];
void dfs0(int i1, int v, int par, int nx)
{
if (!cl[v])
{
if (nx == -1)
l1[i1] = v;
else
g1[i1][v].ad(nx), g1[i1][nx].ad(v);
nx = v;
}
for (auto p : g[i1][v])
{
if (p == par)
continue;
dfs0(i1, p, v, nx);
}
}
void dfs(int i1, int v, int par)
{
pr[i1][v][0] = par;
for (auto p : g[i1][v])
{
if (p == par)
continue;
xr[i1][p] = xr[i1][v] + 1;
dfs(i1, p, v);
}
}
int wk(int i1, int u, int d)
{
for (int i = 0; i < 20; i++)
{
if ((1 << i) & d)
u = pr[i1][u][i];
}
return u;
}
int lca(int i1, int u, int v)
{
if (xr[i1][u] > xr[i1][v])
swap(u, v);
v = wk(i1, v, xr[i1][v] - xr[i1][u]);
if (u == v)
return u;
for (int i = 19; i >= 0; i--)
{
if (pr[i1][u][i] != pr[i1][v][i])
{
u = pr[i1][u][i];
v = pr[i1][v][i];
}
}
return pr[i1][u][0];
}
int a[N][4], sm[N];
int main()
{
fastio;
cin >> n >> k >> q >> t;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
if (x == -1)
{
l[0] = i;
continue;
}
s[0][x]++;
pr[0][i][0] = x;
g[0][x].ad(i);
g[0][i].ad(x);
}
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
if (x == -1)
{
l[1] = i;
continue;
}
s[1][x]++;
pr[1][i][0] = x;
g[1][x].ad(i);
g[1][i].ad(x);
}
priority_queue<pir> qq;
for (int i = 1; i <= n; i++)
qq.push(MP(-max(s[0][i], s[1][i]), i));
for (int i = 0; i < n - k; i++)
{
auto p = qq.top();
qq.pop();
if (cl[p.sc])
continue;
if (p.fr < -1)
assert(0);
cl[p.sc] = 1;
if (p.fr == 0)
{
s[0][pr[0][p.sc][0]]--;
s[1][pr[1][p.sc][0]]--;
qq.push(MP(-max(s[0][pr[0][p.sc][0]], s[1][pr[0][p.sc][0]]), pr[0][p.sc][0]));
qq.push(MP(-max(s[1][pr[1][p.sc][0]], s[1][pr[1][p.sc][0]]), pr[1][p.sc][0]));
}
else if(p.fr == -1)
{
g[0][pr[0][p.sc][0]].clear();
g[0][pr[0][p.sc][0]].ad(g[0][p.sc][0]);
pr[0][g[0][p.sc][0]][0] = pr[0][p.sc][0];
g[1][pr[1][p.sc][0]].clear();
g[1][pr[1][p.sc][0]].ad(g[1][p.sc][0]);
pr[1][g[1][p.sc][0]][0] = pr[1][p.sc][0];
}
}
dfs0(0, l[0], 0, -1);
dfs0(1, l[1], 0, -1);
swap(g, g1), swap(l, l1);
for (int i = 1; i <= n; i++)
if (!cl[i])
cout << i << " ";
cout << endl;
for (int i = 1; i <= n; i++)
{
if (i == l[0] || cl[i])
continue;
cout << "? " << l[0] << " " << i << endl;
}
cout << "!" << endl;
dfs(0, l[0], l[0]);
dfs(1, l[1], l[1]);
for (int i1 : {0, 1})
{
for (int i = 1; i < 20; i++)
{
for (int j = 1; j <= n; j++)
{
if (cl[j])
continue;
pr[i1][j][i] = pr[i1][pr[i1][j][i - 1]][i - 1];
}
}
}
for (int i = 1; i <= n; i++)
{
if (i == l[0] || cl[i])
continue;
for (int j = 0; j < 4; j++)
cin >> a[i][j];
}
for (int i = 1; i <= n; i++)
{
if (cl[i])
continue;
int s = lca(1, i, l[0]);
sm[i] = a[i][3] - a[s][2] + a[l[1]][2];
//cout << i << " " << sm[i] << endl;
}
for (int i = 0; i < t; i++)
{
int u, v;
cin >> u >> v;
//cout << lca(0, u, v) << endl;
cout << a[u][1] + a[v][1] - 2 * a[lca(0, u, v)][1] << " ";
cout << sm[u] + sm[v] - 2 * sm[lca(1, u, v)] << "\n";
}
return 0;
}
/*
__
*(><)*
\/ /
||/
--||
||
/\
/ \
/ \
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
870 ms |
355300 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
986 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2528 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1587 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1579 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
