oj.uz

Submission #709144

# Submission time Handle Problem Language Result Execution time Memory
709144 2023-03-13T06:47:56 Z mansur Prize (CEOI22_prize) C++17
10 / 100
 930 ms 290720 KB 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#include<bits/stdc++.h>	

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define pf push_front
#define pb push_back
#define vt vector
#define s second
#define f first
#define nl '\n'
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
     
vt<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vt<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
 
const int N = 1e6 + 5, mod = 1e9 + 7;

const ll inf = 1e18;
 
double eps = 1e-15;

bool flg = 0;

vt<int> g[2][N], is(N);
vt<pii> s, gr[N];

void dfs(int u, int cnt) {
	is[u] = 1;
	for (int to: g[0][u]) {
		if (sz(s) == cnt) return;
		s.pb({u, to});
		dfs(to, cnt);	
	}
}

int tin[N], tout[N], timer;
pii up[N][18];

void bld(int u) { 
	tin[u] = timer++;
	for (int i = 1; i < 18; i++) {
		up[u][i].f = up[up[u][i - 1].f][i - 1].f;
		up[u][i].s = up[u][i - 1].s + up[up[u][i - 1].f][i - 1].s;
	}
	for (auto [to, w]: gr[u]) {
    	up[to][0] = {u, w};
    	bld(to);
    }
    tout[u] = timer++;
}

bool isp(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	if (isp(a, b)) return a;
	if (isp(b, a)) return b;
	for (int i = 17; i >= 0; i--) {
		if (isp(up[a][i].f, b)) continue;
		a = up[a][i].f;
	}
	return up[a][0].f;
}

int get(int a, int b) {
	if (a == b) return 0;
	int res = 0;
	for (int i = 17; i >= 0; i--) {
		if (isp(up[a][i].f, b)) continue;
		res += up[a][i].s;
		a = up[a][i].f;
	}
	return res + up[a][0].s;
}

void slv() {
	int n, k, q, t;
	cin >> n >> k >> q >> t;
	int r1, r2;
	for (int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		if (p == -1) r1 = i;
		else g[0][p].pb(i);
	}
	for (int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		if (p == -1) r2 = i;
		else g[1][p].pb(i);
	}
	if (q == k - 1) {
		dfs(r1, k - 1);
		for (int i = 1; i <= n; i++) {
			if (is[i]) cout << i << ' ';
		}
		cout << endl;
		for (int i = 0; i < k - 1; i++) {
			cout << "? " << s[i].f << ' ' << s[i].s << nl;
		}
		cout << '!' << endl;
		for (int i = 0; i < k - 1; i++) {
			int x;
			cin >> x >> x >> x >> x;
			gr[s[i].f].pb({s[i].s, x});
		}
	    up[r1][0] = {r1, 0};
	    bld(r1);
	    vt<int> ans;
	    while (t--) {
			int a, b;
			cin >> a >> b;
			int lc = lca(a, b);
			int x = get(a, lc) + get(b, lc);
			ans.pb(x);
	    }
	    for (int i: ans) cout << i << ' ' << i << nl;
	    cout << endl;
	}
}              
 
main() {
	//freopen("shops.in", "r", stdin);                                                                                     
	//freopen("shops.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(0);	                                                                                       
	cin.tie(0);
	int tp = 1;
	if (flg) cin >> tp;
	while (tp--) {  	
		slv();
	}
}

Compilation message

Main.cpp: In function 'void slv()':
Main.cpp:91:10: warning: variable 'r2' set but not used [-Wunused-but-set-variable]
   91 |  int r1, r2;
      |          ^~
Main.cpp: At global scope:
Main.cpp:134:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  134 | main() {
      | ^~~~
Main.cpp: In function 'void slv()':
Main.cpp:120:9: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |      bld(r1);
      |      ~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 188624 KB Output is correct
2 Correct 847 ms 193372 KB Output is correct
3 Correct 532 ms 167100 KB Output is correct
4 Correct 574 ms 166556 KB Output is correct
5 Correct 526 ms 168376 KB Output is correct
6 Correct 639 ms 174628 KB Output is correct
7 Correct 698 ms 174444 KB Output is correct
8 Correct 641 ms 173936 KB Output is correct
9 Correct 548 ms 167056 KB Output is correct
10 Correct 536 ms 168272 KB Output is correct
11 Correct 508 ms 165000 KB Output is correct
12 Correct 524 ms 167876 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 318 ms 105940 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 261 ms 108616 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 541 ms 147356 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 930 ms 290720 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -