oj.uz

답안 #482066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482066 2021-10-22T23:37:56 Z s_samchenko Fountain (eJOI20_fountain) C++17
30 / 100
 407 ms 102260 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;

vector <int> a(N), b(N), d(N);
vector < vector <pii> > g(N);
vector < vector <int> > up(N, vector <int> (20)), sum = up;

void dfs(int v, int pr, int h = 0){
	d[v] = h+1;
	up[v][0] = pr;
	for (auto to : g[v]){
		dfs(to.ff, v, h+1);
		sum[to.ff][0] = to.ss;
	}
}

int get(int r, int v){
	for (int j = 19; j >= 0; --j){
		if (sum[r][j] < v){
			v -= sum[r][j];
			r = up[r][j];
		}
	}
	return r;
}

void solve(){
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
	set <pii> st; st.insert({inf, 0});
	for (int i = 1; i <= n; ++i) st.insert({a[i], i});
	for (int i = 1; i <= n; ++i){
		pii v = *st.upper_bound({a[i], inf});
		g[v.ss].pb({i, b[i]});
		st.erase({a[i], i});
	}

	for (int i = 0; i <= n; ++i)
		if (!d[i]) dfs(i, i);
	for (int j = 1; j < 20; ++j)
		for (int i = 0; i <= n; ++i) up[i][j] = up[up[i][j-1]][j-1];
	for (int j = 1; j < 20; ++j)
		for (int i = 0; i <= n; ++i) sum[i][j] = sum[i][j-1] + sum[up[i][j-1]][j-1];

	while (q--){
		int r, v;
		cin >> r >> v;
		cout << get(r, v) << '\n';
	}

}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 88024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 378 ms 102260 KB Output is correct
2 Correct 407 ms 101660 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 88024 KB Output isn't correct
2 Halted 0 ms 0 KB -