oj.uz

답안 #792469

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
792469 2023-07-25T05:15:57 Z ono_de206 Prize (CEOI22_prize) C++14
54 / 100
 3500 ms 471628 KB 
#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;
}

Compilation message

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1645 ms 261120 KB Output is correct
2 Correct 1628 ms 262856 KB Output is correct
3 Correct 1087 ms 243328 KB Output is correct
4 Correct 1102 ms 243008 KB Output is correct
5 Correct 1131 ms 244856 KB Output is correct
6 Correct 1615 ms 246480 KB Output is correct
7 Correct 1513 ms 246424 KB Output is correct
8 Correct 1512 ms 245972 KB Output is correct
9 Correct 1093 ms 243168 KB Output is correct
10 Correct 1123 ms 244460 KB Output is correct
11 Correct 1060 ms 242204 KB Output is correct
12 Correct 1083 ms 244052 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1806 ms 263120 KB Output is correct
2 Correct 1661 ms 260568 KB Output is correct
3 Correct 1219 ms 243968 KB Output is correct
4 Correct 1284 ms 245920 KB Output is correct
5 Correct 1254 ms 244696 KB Output is correct
6 Correct 1691 ms 245796 KB Output is correct
7 Correct 1759 ms 248072 KB Output is correct
8 Correct 1736 ms 248236 KB Output is correct
9 Correct 1549 ms 248968 KB Output is correct
10 Correct 1552 ms 249604 KB Output is correct
11 Correct 1420 ms 246756 KB Output is correct
12 Correct 1639 ms 249496 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1213 ms 253572 KB Output is correct
2 Correct 1222 ms 253572 KB Output is correct
3 Correct 827 ms 235044 KB Output is correct
4 Correct 802 ms 235136 KB Output is correct
5 Correct 789 ms 235044 KB Output is correct
6 Correct 1140 ms 237880 KB Output is correct
7 Correct 1075 ms 237928 KB Output is correct
8 Correct 1094 ms 237988 KB Output is correct
9 Correct 1008 ms 238364 KB Output is correct
10 Correct 965 ms 238320 KB Output is correct
11 Correct 986 ms 238324 KB Output is correct
12 Correct 942 ms 238364 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3548 ms 455200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3471 ms 471628 KB Output is correct
2 Correct 3484 ms 471296 KB Output is correct
3 Correct 2524 ms 433048 KB Output is correct
4 Correct 2518 ms 436340 KB Output is correct
5 Correct 2419 ms 432708 KB Output is correct
6 Execution timed out 3578 ms 441552 KB Time limit exceeded
7 Halted 0 ms 0 KB -