제출 #792469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
792469		ono_de206	Prize (CEOI22_prize)	C++14	54 / 100	3578 ms	471628 KiB

Main

#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();
      |  ~~~~~~~~~^~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24