QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#395244#8235. Top Clusterqawszx#Compile Error//C++145.8kb2024-04-21 11:35:502024-04-21 11:35:51

Judging History

你现在查看的是最新测评结果

  • [2024-04-21 11:35:51]
  • 评测
查看
  • [2024-04-21 11:35:50]
  • 提交

answer

#pragma GCC diagnostic error "-std=c++11"
#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;
}
源文件, 语言: C++14

详细 

answer.code:1:30: warning: ‘-std=c++11’ is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic error "-std=c++11"
      |                              ^~~~~~~~~~~~
answer.code:23:39: warning: bad option ‘-fwhole-program’ to pragma ‘optimize’ [-Wpragmas]
   23 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
answer.code:30:41: warning: bad option ‘-fstrict-overflow’ to pragma ‘optimize’ [-Wpragmas]
   30 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
answer.code:32:41: warning: bad option ‘-fcse-skip-blocks’ to pragma ‘optimize’ [-Wpragmas]
   32 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
answer.code:46:51: warning: bad option ‘-funsafe-loop-optimizations’ to pragma ‘optimize’ [-Wpragmas]
   46 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
answer.code:52:16: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   52 | long long scan() {
      |                ^
answer.code:52:16: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:52:16: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:52:16: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:59:17: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   59 | void print(int x) {
      |                 ^
answer.code:59:17: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:59:17: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:59:17: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:69:28: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   69 | void getEuler(int u, int fa) {
      |                            ^
answer.code:69:28: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:69:28: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:69:28: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:78:13: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   78 | void initST() {
      |             ^
answer.code:78:13: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:78:13: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:78:13: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:86:40: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   86 | std::pair<int, int> getMin(int l, int r) {
      |                                        ^
answer.code:86:40: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:86:40: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:86:40: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:91:30: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   91 | long long getDis(int u, int v) {
      |                              ^
answer.code:91:30: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:91:30: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:91:30: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:96:27: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   96 | void prepare(int u, int fa) {
      |                           ^
answer.code:96:27: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:96:27: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:96:27: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:108:22: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
  108 | void construct(int fa) {
      |                      ^
answer.code:108:22: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:108:22: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:108:22: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code: In function ‘void construct(int)’:
answer.code:125:21: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
  125 |     [&](int x, int y) { return getDis(x, u) < getDis(y, u); });
      |                     ^
answer.code:125:21:...
English 繁體中文 简体中文

服务器时间: 2024-12-05 03:43:47 | 开源项目