oj.uz

답안 #791635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791635 2023-07-24T08:24:07 Z ono_de206 Prize (CEOI22_prize) C++14
0 / 100
 3500 ms 728080 KB 
#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;}

const int mxn = 1010;
pair<int , int> P[2][mxn];
int dis[2][mxn][mxn], lca[2][mxn][mxn];

struct tree {
	int n, lg, cnt;
	vector<int> dep;
	vector<vector<int>> jump, g;
	bool did;

	tree(int _n) : n(_n) {
		dep.resize(n + 1);
		g.resize(n + 1);
		did = 0;
		lg = cnt = 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;
		for(int x : g[to]) {
			if(x == fr) continue;
			build(x, to);
		}
	}

	void add(int x, int y) {
		g[x].pb(y);
		g[y].pb(x);
		cnt++;
		if(cnt == n - 1) build();
	}

	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) {
		buildLCA();
		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];
	}

	bool isOn(int x, int y, int z) {
		int p = lca(x, y);
		if(dep[p] > dep[z]) return 0;
		return (lca(x, z) == z || lca(y, z) == z);
	}
};

void go() {
	int n, k, q, t;
	cin >> n >> k >> q >> t;
	tree t1(n), t2(n);
	for(int i = 1, x; i <= n; i++) {
		cin >> x;
		if(x != -1) t1.add(x, i);
	}
	for(int i = 1, x; i <= n; i++) {
		cin >> x;
		if(x != -1) t2.add(x, i);
	}

	for(int i = 1; i <= k; i++) {
		cout << i << " \n"[i == k];
	}
	cout.flush();

	for(int i = 1; i < k; i++) {
		cout << "? " << i << ' ' << i + 1 << '\n';
	}
	cout << "!\n";
	cout.flush();

	for(int i = 2; i <= k; i++) {
		cin >> P[0][i].ff >> P[0][i].ss >> P[1][i].ff >> P[1][i].ss;
	}

	for(int i = 1; i <= k; i++) {
		for(int j = i; j <= k; j++) {
			lca[0][i][j] = t1.lca(i, j);
			lca[1][i][j] = t2.lca(i, j);
		}
	}

	for(int i = 1; i <= k; i++) {
		for(int p = 0; p < 2; p++) {
			pair<int, int> dp{0, 0};
			int ls = i;
			for(int j = i + 1; j <= k; j++) {
				if(lca[p][i][j] == lca[p][ls][j]) dp = {P[p][j].ff - dp.ss + dp.ff, P[p][j].ss};
				else if(lca[p][i][j] == lca[p][i][ls]) dp.ss = P[p][j].ss - P[p][j].ff;
				else continue;
				ls = j;
				dis[p][i][j] = dp.ff + dp.ss;
			}
		}
	}

	for(int i = k; i >= 1; i--) {
		for(int p = 0; p < 2; p++) {
			pair<int, int> dp{0, 0};
			int ls = i;
			for(int j = i - 1; j >= 1; j--) {
				if(lca[p][i][j] == lca[p][ls][j]) dp = {P[p][j].ss - dp.ss + dp.ff, P[p][j + 1].ff};
				else if(lca[p][i][j] == lca[p][i][ls]) dp.ss = P[p][j + 1].ff - P[p][j + 1].ss;
				else continue;
				ls = j;
				dis[p][j][i] = dp.ff + dp.ss;
			}
		}
	}

	vector<pair<int, int>> Q;
	for(int i = 1, x, y; i <= t; i++) {
		cin >> x >> y;
		if(x > y) swap(x, y);
		Q.eb(x, y);
	}
	for(auto it : Q) {
		cout << dis[0][it.ff][it.ss] << ' ' << dis[1][it.ff][it.ss] << '\n';
		cout.flush();
	}
}
 
signed main() {
	// #ifndef ONO
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	// #endif
	// fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1231 ms 377472 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1056 ms 386696 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1344 ms 193308 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

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

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2511 ms 728080 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -