제출 #792469

#제출 시각아이디문제언어결과실행 시간메모리
792469ono_de206Prize (CEOI22_prize)C++14
54 / 100
3578 ms471628 KiB
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #pragma GCC optimize(3) #pragma GCC target("avx") #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> using namespace std; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define in insert #define all(x) x.begin(),x.end() #define pb push_back #define eb emplace_back #define ff first #define ss second // #define int long long typedef long long ll; typedef vector<int> vi; typedef set<int> si; typedef multiset<int> msi; typedef pair<int, int> pii; typedef vector<pii> vpii; template<typename T, typename U> ostream & operator << (ostream &out, const pair<T, U> &c) { out << c.first << ' ' << c.second; return out; } template<typename T> ostream & operator << (ostream &out, vector<T> &v) { const int sz = v.size(); for (int i = 0; i < sz; i++) { if (i) out << ' '; out << v[i]; } return out; } template<typename T> istream & operator >> (istream &in, vector<T> &v) { for (T &x : v) in >> x; return in; } template<typename T> void mxx(T &a, T b){if(b > a) a = b;} template<typename T> void mnn(T &a, T b){if(b < a) a = b;} struct tree { int n, lg, t; vector<int> dep, in, out; vector<vector<int>> jump, g; bool did; tree(int _n) : n(_n) { g.resize(n + 1); in.resize(n + 1); out.resize(n + 1); dep.resize(n + 1); did = 0; lg = t = 0; while((1 << lg) <= n) lg++; jump.resize(n + 1, vector<int>(lg)); } void build(int to = 1, int fr = 0) { dep[to] = dep[fr] + 1; jump[to][0] = fr; in[to] = ++t; for(int x : g[to]) { if(x == fr) continue; build(x, to); } out[to] = t; } void add(int x, int y) { g[x].pb(y); g[y].pb(x); } void buildLCA() { if(did) return; did = 1; for(int j = 1; j < lg; j++) { for(int i = 1; i <= n; i++) { jump[i][j] = jump[jump[i][j - 1]][j - 1]; } } } int lca(int x, int y) { if(dep[x] < dep[y]) swap(x, y); int dff = dep[x] - dep[y]; for(int i = 0; i < lg; i++) { if((dff >> i) & 1) x = jump[x][i]; } if(x == y) return x; for(int i = lg - 1; i >= 0; i--) { if(jump[x][i] != jump[y][i]) { x = jump[x][i]; y = jump[y][i]; } } return jump[x][0]; } int distance(int x, int y) { return dep[x] + dep[y] - dep[lca(x, y)] * 2; } bool isAnc(int x, int y) { return in[x] <= in[y] && out[x] >= out[y]; } bool isOn(int x, int y, int z) { int p = lca(x, y); if(dep[p] > dep[z]) return 0; return (isAnc(z, x) || isAnc(z, y)); } ~tree() { jump.clear(); dep.clear(); g.clear(); in.clear(); out.clear(); } }; const int mxn = 1e6 + 10; int dis1[mxn], dis2[mxn]; bool vis[mxn]; vector<pair<int, int>> adj1[mxn], adj2[mxn]; void dfs1(int to, int dis) { dis1[to] = dis; vis[to] = 1; for(auto it : adj1[to]) { if(vis[it.ff]) continue; dfs1(it.ff, dis + it.ss); } } void dfs2(int to, int dis) { dis2[to] = dis; vis[to] = 1; for(auto it : adj2[to]) { if(vis[it.ff]) continue; dfs2(it.ff, dis + it.ss); } } int main() { fast; int n, k, q, t; cin >> n >> k >> q >> t; tree tr1(n), tr2(n); int root1, root2; for(int i = 1; i <= n; i++) { int x; cin >> x; if(~x) tr1.add(x, i); else root1 = i; } for(int i = 1; i <= n; i++) { int x; cin >> x; if(~x) tr2.add(x, i); else root2 = i; } tr1.build(root1); tr1.buildLCA(); tr2.build(root2); tr2.buildLCA(); vector<int> ks; for(int i = 1; i <= n; i++) { if(tr1.in[i] <= k) ks.pb(i); } sort(all(ks), [&](int x, int y) { return tr2.in[x] < tr2.in[y]; }); for(int i = 0; i < k; i++) { cout << ks[i] << ' '; } cout << endl; for(int i = 0; i + 1 < k; i++) { cout << "? " << ks[i] << ' ' << ks[i + 1] << endl; } cout << "!" << endl; for(int i = 0; i + 1 < k; i++) { int a, b, c, d; cin >> a >> b >> c >> d; int lc1 = tr1.lca(ks[i], ks[i + 1]); int lc2 = tr2.lca(ks[i], ks[i + 1]); adj1[ks[i]].eb(lc1, -a); adj1[lc1].eb(ks[i + 1], b); adj2[ks[i]].eb(lc2, -c); adj2[lc2].eb(ks[i + 1], d); } dfs1(ks[0], 0); for(int i = 0; i < k; i++) { vis[ks[i]] = 0; } dfs2(ks[0], 0); vector<pair<int, int>> ans; for(int i = 0; i < t; i++) { int x, y; cin >> x >> y; ans.eb(dis1[x] + dis1[y] - dis1[tr1.lca(x, y)] * 2, dis2[x] + dis2[y] - dis2[tr2.lca(x, y)] * 2); } for(auto &it : ans) { cout << it << endl; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:23:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   23 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
Main.cpp:30:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   30 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
Main.cpp:32:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
Main.cpp:46:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   46 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
Main.cpp:70:57: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   70 | ostream & operator << (ostream &out, const pair<T, U> &c) {
      |                                                         ^
Main.cpp:70:57: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:70:57: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:70:57: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:76:50: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   76 | ostream & operator << (ostream &out, vector<T> &v) {
      |                                                  ^
Main.cpp:76:50: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:76:50: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:76:50: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:86:49: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   86 | istream & operator >> (istream &in, vector<T> &v) {
      |                                                 ^
Main.cpp:86:49: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:86:49: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:86:49: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:93:19: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   93 | void mxx(T &a, T b){if(b > a) a = b;}
      |                   ^
Main.cpp:93:19: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:93:19: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:93:19: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:95:19: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   95 | void mnn(T &a, T b){if(b < a) a = b;}
      |                   ^
Main.cpp:95:19: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:95:19: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:95:19: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:103:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  103 |  tree(int _n) : n(_n) {
      |             ^
Main.cpp:103:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:103:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:103:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:114:35: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  114 |  void build(int to = 1, int fr = 0) {
      |                                   ^
Main.cpp:114:35: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:114:35: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:114:35: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:125:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  125 |  void add(int x, int y) {
      |                       ^
Main.cpp:125:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:125:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:125:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:130:16: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  130 |  void buildLCA() {
      |                ^
Main.cpp:130:16: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:130:16: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:130:16: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:140:22: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  140 |  int lca(int x, int y) {
      |                      ^
Main.cpp:140:22: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:140:22: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:140:22: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:156:27: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  156 |  int distance(int x, int y) {
      |                           ^
Main.cpp:156:27: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:156:27: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:156:27: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:160:25: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  160 |  bool isAnc(int x, int y) {
      |                         ^
Main.cpp:160:25: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:160:25: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:160:25: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:164:31: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  164 |  bool isOn(int x, int y, int z) {
      |                               ^
Main.cpp:164:31: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:164:31: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:164:31: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:170:8: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  170 |  ~tree() {
      |        ^
Main.cpp:170:8: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:170:8: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:170:8: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:184:26: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  184 | void dfs1(int to, int dis) {
      |                          ^
Main.cpp:184:26: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:184:26: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:184:26: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:193:26: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  193 | void dfs2(int to, int dis) {
      |                          ^
Main.cpp:193:26: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:193:26: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:193:26: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:202:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  202 | int main() {
      |          ^
Main.cpp:202:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:202:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:202:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp: In function 'int main()':
Main.cpp:225:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  225 |  sort(all(ks), [&](int x, int y) {
      |                                ^
Main.cpp:225:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
Main.cpp:225:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
Main.cpp:225:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
Main.cpp:218:11: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  218 |  tr1.build(root1); tr1.buildLCA();
      |  ~~~~~~~~~^~~~~~~
Main.cpp:219:11: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  219 |  tr2.build(root2); tr2.buildLCA();
      |  ~~~~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...