oj.uz

답안 #968376

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968376 2024-04-23T11:08:29 Z marvinthang Prize (CEOI22_prize) C++17
100 / 100
 2187 ms 269352 KB 
/*************************************
*    author: marvinthang             *
*    created: 23.04.2024 17:01:12    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

const int LOG = 18;

int n, k, q, t;
vector <bool> choosed;

struct Tree {
	int n, rt;
	vector <vector <int>> adj;
	Tree(int _n = 0) {
		n = _n;
		adj.resize(n + 1);
		FORE(u, 1, n) {
			int p; cin >> p;
			if (p == -1) rt = u;
			else adj[p].push_back(u);
		}
	}
	vector <int> get_first_k(void) {
		vector <int> res{rt};
		for (int i = 0; (int) res.size() < k; ++i) res.insert(res.end(), ALL(adj[res[i]]));
		res.resize(k);
		return res;
	}
	vector <int> get_order(void) {
		vector <int> res;
		stack <int> st;
		st.push(rt);
		while (!st.empty()) {
			int u = st.top(); st.pop();
			if (choosed[u]) res.push_back(u);
			for (int v: adj[u]) st.push(v);
		}
		return res;
	}
	vector <int> ver, pos, depth, dist;
	vector <array <int, LOG>> anc;
	vector <vector <int>> tadj;
	vector <vector <pair <int, int>>> fadj;
	int dfs(int u) {
		vector <int> child;
		for (int v: adj[u]) {
			v = dfs(v);
			if (v != -1) child.push_back(v);
		}
		if (choosed[u] || (int) child.size() > 1) {
			pos[u] = ver.size();
			ver.push_back(u);
			tadj.push_back(child);
			return pos[u];
		}
		if ((int) child.size() == 1) return child[0];
		return -1;
	}
	int get_lca(int u, int v) {
		u = pos[u]; v = pos[v];
		if (depth[u] < depth[v]) swap(u, v);
		REPD(i, LOG) if (depth[anc[u][i]] >= depth[v]) u = anc[u][i];
		if (u == v) return ver[u];
		REPD(i, LOG) if (anc[u][i] != anc[v][i]) {
			u = anc[u][i];
			v = anc[v][i];
		}
		return ver[anc[u][0]];
	}
	void rebuild(void) {
		pos.resize(n + 1);
		dfs(rt);
		n = ver.size();
		depth.resize(n);
		anc.resize(n);
		queue <int> q;
		q.push(n - 1);
		anc[n - 1][0] = n - 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int v: tadj[u]) {
				depth[v] = depth[u] + 1;
				anc[v][0] = u;
				q.push(v);
			}
		}
		FOR(k, 1, LOG) REP(u, n) anc[u][k] = anc[anc[u][k - 1]][k - 1];
		fadj.resize(n);
	}
	void add_edge(int u, int v, int w) {
		u = pos[u]; v = pos[v];
		fadj[u].emplace_back(w, v);
		fadj[v].emplace_back(-w, u);
	}
	void build_weights(void) {
		dist.assign(n, -1);
		dist[n - 1] = 0;
		queue <int> q;
		q.push(n - 1);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (auto [w, v]: fadj[u]) if (dist[v] == -1) {
				dist[v] = dist[u] + w;
				q.push(v);
			}
		}
	}
	int get_dist(int u, int v) {
		return dist[pos[u]] + dist[pos[v]] - 2 * dist[pos[get_lca(u, v)]];
	}
};

void process(void) {
	cin >> n >> k >> q >> t;
	choosed.resize(n + 1);
	Tree first(n), second(n);
	vector <int> lst = first.get_first_k();
	for (int x: lst) {
		choosed[x] = true;
		cout << x << ' ';
	}
	cout << endl;
	vector <int> se_order = second.get_order();
	first.rebuild();
	second.rebuild();
	REP(i, k - 1) cout << "? " << se_order[i] << ' ' << se_order[i + 1] << '\n';
	cout << "!" << endl;
	REP(i, k - 1) {
		int u = se_order[i], v = se_order[i + 1];
		int l1 = first.get_lca(u, v);
		int l2 = second.get_lca(u, v);
		int a, b, c, d; cin >> a >> b >> c >> d;
		first.add_edge(l1, u, a);
		first.add_edge(l1, v, b);
		second.add_edge(l2, u, c);
		second.add_edge(l2, v, d);
	}
	first.build_weights();
	second.build_weights();
	vector <pair <int, int>> res;
	while (t--) {
		int u, v; cin >> u >> v;
		res.emplace_back(first.get_dist(u, v), second.get_dist(u, v));
	}
	for (auto [u, v]: res) cout << u << ' ' << v << '\n';
	cout.flush();
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("prize");
	// int t; cin >> t; while (t--)
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:190:2: note: in expansion of macro 'file'
  190 |  file("prize");
      |  ^~~~
Main.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:190:2: note: in expansion of macro 'file'
  190 |  file("prize");
      |  ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 967 ms 143704 KB Output is correct
2 Correct 992 ms 155068 KB Output is correct
3 Correct 561 ms 73620 KB Output is correct
4 Correct 623 ms 72508 KB Output is correct
5 Correct 638 ms 82276 KB Output is correct
6 Correct 782 ms 93444 KB Output is correct
7 Correct 820 ms 94936 KB Output is correct
8 Correct 731 ms 91652 KB Output is correct
9 Correct 621 ms 75308 KB Output is correct
10 Correct 669 ms 80560 KB Output is correct
11 Correct 513 ms 67936 KB Output is correct
12 Correct 654 ms 77700 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1069 ms 155476 KB Output is correct
2 Correct 886 ms 138452 KB Output is correct
3 Correct 667 ms 77508 KB Output is correct
4 Correct 680 ms 86624 KB Output is correct
5 Correct 694 ms 82400 KB Output is correct
6 Correct 770 ms 87504 KB Output is correct
7 Correct 886 ms 100284 KB Output is correct
8 Correct 950 ms 101612 KB Output is correct
9 Correct 841 ms 100536 KB Output is correct
10 Correct 791 ms 104612 KB Output is correct
11 Correct 705 ms 88452 KB Output is correct
12 Correct 826 ms 103864 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 636 ms 115688 KB Output is correct
2 Correct 598 ms 115636 KB Output is correct
3 Correct 371 ms 45216 KB Output is correct
4 Correct 358 ms 45736 KB Output is correct
5 Correct 328 ms 45144 KB Output is correct
6 Correct 479 ms 59676 KB Output is correct
7 Correct 498 ms 59148 KB Output is correct
8 Correct 489 ms 59448 KB Output is correct
9 Correct 573 ms 57256 KB Output is correct
10 Correct 555 ms 57540 KB Output is correct
11 Correct 553 ms 58044 KB Output is correct
12 Correct 431 ms 57268 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1634 ms 229888 KB Output is correct
2 Correct 1662 ms 230232 KB Output is correct
3 Correct 1068 ms 89840 KB Output is correct
4 Correct 1037 ms 90372 KB Output is correct
5 Correct 1028 ms 90256 KB Output is correct
6 Correct 1391 ms 118840 KB Output is correct
7 Correct 1296 ms 118540 KB Output is correct
8 Correct 1330 ms 118564 KB Output is correct
9 Correct 1221 ms 113748 KB Output is correct
10 Correct 1290 ms 113936 KB Output is correct
11 Correct 1247 ms 114184 KB Output is correct
12 Correct 1231 ms 114604 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2187 ms 269352 KB Output is correct
2 Correct 2132 ms 267960 KB Output is correct
3 Correct 1260 ms 119424 KB Output is correct
4 Correct 1427 ms 137024 KB Output is correct
5 Correct 1211 ms 117160 KB Output is correct
6 Correct 1777 ms 166512 KB Output is correct
7 Correct 1589 ms 147140 KB Output is correct
8 Correct 1734 ms 157720 KB Output is correct
9 Correct 1654 ms 151756 KB Output is correct
10 Correct 1600 ms 147336 KB Output is correct
11 Correct 1584 ms 148240 KB Output is correct
12 Correct 1564 ms 156896 KB Output is correct