QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #395245 | #8235. Top Cluster | qawszx# | Compile Error | / | / | C++14 | 5.8kb | 2024-04-21 11:36:18 | 2024-04-21 11:36:18 |
Judging History
answer
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
long long scan() {
long long x = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
return x;
}
int top, stk[11];
void print(int x) {
do stk[++top] = x % 10, x /= 10; while (x);
while (top) putchar(stk[top--] + '0');
}
const int N = 5e5 + 5;
int n, Q, id[N], ansmx, Fa[N], ans[N];
bool idv[N];
std::vector<std::pair<int, int>> ver[N];
int eulerc, euler[2 * N], apr[N], dep[N]; long long dis[N];
void getEuler(int u, int fa) {
euler[++eulerc] = u, apr[u] = eulerc;
for (auto it: ver[u]) {
int v = it.first, w = it.second;
if (v == fa) continue;
dep[v] = dep[u] + 1, dis[v] = dis[u] + w, getEuler(v, u), euler[++eulerc] = u;
}
}
int lg2[2 * N]; std::pair<int, int> st[2 * N][19];
void initST() {
for (int i = 2; i <= eulerc; ++i) lg2[i] = lg2[i >> 1] + 1;
for (int i = 1; i <= eulerc; ++i)
st[i][0] = std::make_pair(dep[euler[i]], euler[i]);
for (int j = 1; j < 19; ++j)
for (int i = 1; i + (1 << j) - 1 <= eulerc; ++i)
st[i][j] = std::min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
std::pair<int, int> getMin(int l, int r) {
if (l > r) std::swap(l, r);
int x = lg2[r - l + 1];
return std::min(st[l][x], st[r - (1 << x) + 1][x]);
}
long long getDis(int u, int v) {
return dis[u] + dis[v] - 2 * dis[getMin(apr[u], apr[v]).second];
}
int fullSz, sz[N], msz[N];
bool vis[N]; std::vector<int> vec;
void prepare(int u, int fa) {
++fullSz, sz[u] = 1, msz[u] = 0; vec.push_back(u);
for (auto it: ver[u]) {
int v = it.first;
if (vis[v] || v == fa) continue;
prepare(v, u); sz[u] += sz[v], msz[u] = std::max(msz[u], sz[v]);
}
}
int divFa[N];
std::unordered_map<int, int> whr[N];
std::vector<int> arr[N];
std::vector<std::pair<int, int>> res[N];
void construct(int fa) {
int u = 0;
for (auto v: vec) {
msz[v] = std::max(msz[v], fullSz - sz[v]);
if (!u || msz[v] < msz[u]) u = v;
}
vis[u] = true, divFa[u] = fa;
arr[u] = vec;
for (auto it: ver[u]) {
int v = it.first;
if (vis[v]) continue;
fullSz = 0; vec.clear();
prepare(v, 0);
for (auto x: vec) whr[u][x] = v;
construct(u);
}
std::sort(arr[u].begin(), arr[u].end(),
[&](int x, int y) { return getDis(x, u) < getDis(y, u); });
res[u].resize(arr[u].size());
int sz = arr[u].size();
int mn = 0, cmn = 0;
for (int i = sz - 1; i >= 0; --i) {
int v = arr[u][i];
if (mn == 0) mn = v;
else {
if (whr[u][mn] == whr[u][v]) {
if (id[v] < id[mn]) mn = v;
}
else if (whr[u][cmn] == whr[u][v]) {
if (id[v] < id[cmn]) cmn = v;
}
else {
if (id[v] < id[mn]) cmn = mn, mn = v;
else if (id[v] < id[cmn]) cmn = v;
}
if (id[mn] > id[cmn]) std::swap(mn, cmn);
}
res[u][i] = std::make_pair(mn, cmn);
}
}
int main() {
n = scan(), Q = scan();
id[0] = 1e9 + 9;
for (int i = 1; i <= n; ++i) {
id[i] = scan(); if (id[i] < N) idv[id[i]] = true;
}
for (int i = 0; i < N; ++i) if (!idv[i]) { ansmx = i; break; }
for (int i = 1; i < n; ++i) {
int u = scan(), v = scan(), w = scan();
ver[u].emplace_back(v, w), ver[v].emplace_back(u, w);
}
getEuler(1, 0); initST(); prepare(1, 0); construct(0);
while (Q--) {
int u = scan(), ask = u; long long d = scan(); int ans = ansmx;
while (u) {
int sz = arr[u].size();
int l = 0, r = sz;
long long k = d - getDis(ask, u);
while (l < r) {
int mid = (l + r) >> 1;
if (getDis(arr[u][mid], u) <= k) l = mid + 1;
else r = mid;
}
if (l < sz) {
std::pair<int, int> it = res[u][l];
if (whr[u][it.first] == whr[u][ask]) ans = std::min(ans, id[it.second]);
else ans = std::min(ans, id[it.first]);
}
u = divFa[u];
}
print(ans), putchar('\n');
}
return 0;
}
Details
answer.code:22:39: warning: bad option ‘-fwhole-program’ to pragma ‘optimize’ [-Wpragmas]
22 | #pragma GCC optimize("-fwhole-program")
| ^
answer.code:29:41: warning: bad option ‘-fstrict-overflow’ to pragma ‘optimize’ [-Wpragmas]
29 | #pragma GCC optimize("-fstrict-overflow")
| ^
answer.code:31:41: warning: bad option ‘-fcse-skip-blocks’ to pragma ‘optimize’ [-Wpragmas]
31 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
answer.code:45:51: warning: bad option ‘-funsafe-loop-optimizations’ to pragma ‘optimize’ [-Wpragmas]
45 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
answer.code:51:16: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
51 | long long scan() {
| ^
answer.code:51:16: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:51:16: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:51:16: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:58:17: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
58 | void print(int x) {
| ^
answer.code:58:17: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:58:17: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:58:17: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:68:28: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
68 | void getEuler(int u, int fa) {
| ^
answer.code:68:28: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:68:28: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:68:28: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:77:13: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
77 | void initST() {
| ^
answer.code:77:13: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:77:13: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:77:13: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:85:40: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
85 | std::pair<int, int> getMin(int l, int r) {
| ^
answer.code:85:40: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:85:40: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:85:40: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:90:30: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
90 | long long getDis(int u, int v) {
| ^
answer.code:90:30: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:90:30: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:90:30: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:95:27: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
95 | void prepare(int u, int fa) {
| ^
answer.code:95:27: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:95:27: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:95:27: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:107:22: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
107 | void construct(int fa) {
| ^
answer.code:107:22: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:107:22: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:107:22: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code: In function ‘void construct(int)’:
answer.code:124:21: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
124 | [&](int x, int y) { return getDis(x, u) < getDis(y, u); });
| ^
answer.code:124:21: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:124:21: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:1...