oj.uz

답안 #328455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
328455 2020-11-16T16:43:07 Z BeanZ Klasika (COCI20_klasika) C++14
33 / 110
 742 ms 524292 KB 
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 3e5 + 5;
const int mod = 123456789;
const long long oo = 1e18;
ll timer = 1, timer2 = 0, timer3 = 1;
ll cost[N], tin[N], tout[N], dp[N * 32][2];
vector<ll> node[N];
set<ll> mem[N * 32];
void dfs(ll u){
    timer2++;
    tin[u] = timer2;
    for (auto j : node[u]){
        dfs(j);
    }
    tout[u] = timer2;
}
void add(ll u, ll p){
    ll now = 1;
    for (int i = 30; i >= 0; i--){
        ll a = ((u & (1 << i)) > 0);
        if (dp[now][a] == 0){
            timer3++;
            dp[now][a] = timer3;
        }
        now = dp[now][a];
        mem[now].insert(p);
    }
}
ll get(ll u, ll l, ll r){
    ll now = 1;
    ll res = 0;
    for (int i = 30; i >= 0; i--){
        ll a = ((u & (1 << i)) > 0);
        ll id = dp[now][1 - a];
        bool flag = true;
        auto it = mem[id].lower_bound(l);
        if (it == mem[id].end() || (*it) > r) flag = false;
        if (flag){
            res = res + (1 << i);
            now = id;
        } else {
            now = dp[now][a];
        }
        /*
        if (u == 0){
            if (it == mem[id].end()) cout << -1 << " ";
            else cout << (*it) << " ";
            cout << id << " ";
        }*/
    }
    //cout << now << " " << res << endl;
    return res;
}
string task[N];
ll x[N], y[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll q;
    cin >> q;
    for (int i = 1; i <= q; i++){
        cin >> task[i];
        if (task[i] == "Add"){
            cin >> x[i] >> y[i];
            timer++;
            cost[timer] = cost[x[i]] ^ y[i];
            node[x[i]].push_back(timer);
            x[i] = timer;
        } else {
            cin >> x[i] >> y[i];
        }
    }
    dfs(1);
    add(0, tin[1]);
    for (int i = 1; i <= q; i++){
        if (task[i] == "Add"){
            add(cost[x[i]], tin[x[i]]);
        } else {
            cout << get(cost[x[i]], tin[y[i]], tout[y[i]]) << endl;
        }
    }
    //cout << dp[1][0] << endl;
}
/*
3
Add 1 9
Add 2 3
Query 1 2
*/

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   64 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 262 ms 467948 KB Output is correct
2 Correct 266 ms 467820 KB Output is correct
3 Correct 267 ms 467948 KB Output is correct
4 Correct 265 ms 468076 KB Output is correct
5 Correct 275 ms 467828 KB Output is correct
6 Correct 269 ms 467820 KB Output is correct
7 Correct 262 ms 467948 KB Output is correct
8 Correct 266 ms 467948 KB Output is correct
9 Correct 263 ms 467820 KB Output is correct
10 Correct 266 ms 467948 KB Output is correct
11 Correct 268 ms 467948 KB Output is correct
12 Correct 262 ms 468076 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 262 ms 467948 KB Output is correct
2 Correct 266 ms 467820 KB Output is correct
3 Correct 267 ms 467948 KB Output is correct
4 Correct 265 ms 468076 KB Output is correct
5 Correct 275 ms 467828 KB Output is correct
6 Correct 269 ms 467820 KB Output is correct
7 Correct 262 ms 467948 KB Output is correct
8 Correct 266 ms 467948 KB Output is correct
9 Correct 263 ms 467820 KB Output is correct
10 Correct 266 ms 467948 KB Output is correct
11 Correct 268 ms 467948 KB Output is correct
12 Correct 262 ms 468076 KB Output is correct
13 Correct 268 ms 468588 KB Output is correct
14 Correct 265 ms 469356 KB Output is correct
15 Correct 279 ms 470124 KB Output is correct
16 Correct 270 ms 470788 KB Output is correct
17 Correct 269 ms 468716 KB Output is correct
18 Correct 266 ms 469228 KB Output is correct
19 Correct 272 ms 469996 KB Output is correct
20 Correct 273 ms 470764 KB Output is correct
21 Correct 275 ms 468660 KB Output is correct
22 Correct 270 ms 469228 KB Output is correct
23 Correct 271 ms 470124 KB Output is correct
24 Correct 273 ms 470636 KB Output is correct

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 742 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 262 ms 467948 KB Output is correct
2 Correct 266 ms 467820 KB Output is correct
3 Correct 267 ms 467948 KB Output is correct
4 Correct 265 ms 468076 KB Output is correct
5 Correct 275 ms 467828 KB Output is correct
6 Correct 269 ms 467820 KB Output is correct
7 Correct 262 ms 467948 KB Output is correct
8 Correct 266 ms 467948 KB Output is correct
9 Correct 263 ms 467820 KB Output is correct
10 Correct 266 ms 467948 KB Output is correct
11 Correct 268 ms 467948 KB Output is correct
12 Correct 262 ms 468076 KB Output is correct
13 Correct 268 ms 468588 KB Output is correct
14 Correct 265 ms 469356 KB Output is correct
15 Correct 279 ms 470124 KB Output is correct
16 Correct 270 ms 470788 KB Output is correct
17 Correct 269 ms 468716 KB Output is correct
18 Correct 266 ms 469228 KB Output is correct
19 Correct 272 ms 469996 KB Output is correct
20 Correct 273 ms 470764 KB Output is correct
21 Correct 275 ms 468660 KB Output is correct
22 Correct 270 ms 469228 KB Output is correct
23 Correct 271 ms 470124 KB Output is correct
24 Correct 273 ms 470636 KB Output is correct
25 Runtime error 742 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -