oj.uz

Submission #377541

# Submission time Handle Problem Language Result Execution time Memory
377541 2021-03-14T09:55:49 Z kartel Specijacija (COCI20_specijacija) C++14
0 / 110
 76 ms 68608 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = (1000 + 1) * (1000 + 2) + 50;

vector <int> g[N];
int up[N][25];
int n, q, t;

int to[N], mk[N];
vector <int> lv[1050];
int nm[N];
int tin[N], tout[N], tim;

void dfs(int v, int pr) {
    tin[v] = tim++;

    up[v][0] = pr;

    for (auto u : g[v]) {
        if (u == pr) {
            continue;
        }

        dfs(u, v);
    }

    tout[v] = tim++;
}

int isa(int x, int y) {return (tin[x] <= tin[y] && tout[x] >= tout[y]);}

int lca(int x, int y) {
    if (isa(x, y)) {
        return x;
    }

    if (isa(y, x)) {
        return y;
    }

    for (int st = 21; st >= 0; st--) {
        if (!isa(up[y][st], x)) {
            y = up[y][st];
        }
    }

    return up[y][0];
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();

    cin >> n >> q >> t;

    for (int i = 1; i <= n + 1; i++) {
        for (int j = i * (i - 1) / 2 + 1; j <= i * (i + 1) / 2; j++) {
            nm[j] = sz(lv[i]);
            lv[i].pb(j);
        }
    }

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        mk[x] = 1;
        g[x].pb(lv[i + 1][nm[x]]);
        g[x].pb(lv[i + 1][nm[x] + 1]);

        to[lv[i + 1][nm[x]]] = 1;
        to[lv[i + 1][nm[x] + 1]] = 1;
    }

    for (int i = 1; i <= n; i++) {
        int k = 0;
        for (int j = i * (i - 1) / 2 + 1; j <= i * (i + 1) / 2; j++) {
            if (mk[j]) {
                continue;
            }

            while (to[lv[i + 1][k]]) {
                k++;
            }

            g[j].pb(lv[i + 1][k]);
            k++;
        }
    }

    tin[0] = tim++;
    tout[0] = 1e9;

    dfs(1, 0);

    for (int st = 1; st <= 21; st++) {
        for (int i = 1; i <= (n + 1) * (n + 2); i++) {
            up[i][st] = up[up[i][st - 1]][st - 1];
        }
    }

    while (q--) {
        int x, y;
        cin >> x >> y;

        cout << lca(x, y) << el;
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 68608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 68608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 68608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 76 ms 68332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -