oj.uz

Submission #709145

# Submission time Handle Problem Language Result Execution time Memory
709145 2023-03-13T06:49:01 Z vjudge1 Prize (CEOI22_prize) C++17
10 / 100
 803 ms 290836 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 594 ms 188692 KB Output is correct
2 Correct 644 ms 193356 KB Output is correct
3 Correct 512 ms 167196 KB Output is correct
4 Correct 461 ms 166476 KB Output is correct
5 Correct 523 ms 168328 KB Output is correct
6 Correct 594 ms 174788 KB Output is correct
7 Correct 598 ms 174508 KB Output is correct
8 Correct 638 ms 173944 KB Output is correct
9 Correct 482 ms 167068 KB Output is correct
10 Correct 495 ms 168116 KB Output is correct
11 Correct 486 ms 165012 KB Output is correct
12 Correct 497 ms 168020 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 322 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 243 ms 108600 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 492 ms 147304 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 803 ms 290836 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -