oj.uz

Submission #411591

# Submission time Handle Problem Language Result Execution time Memory
411591 2021-05-25T14:47:33 Z Aldas25 Inside information (BOI21_servers) C++14
50 / 100
 302 ms 54024 KB 
//#pragma GCC optimize ("03")
//#pragma GCC optimize ("0fast")
//#pragma GCC optimize ("02")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target ("avx2")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vl;

const int MAXN = 500100, MAXK = 20;

int n, k;
vector<pair<char, pii>> queries;

vii adj[MAXN];
int par[MAXN][MAXK];
int dep[MAXN];
int longMaz[MAXN], longDid[MAXN];
int mx[MAXN][MAXK];

void dfs (int v, int p, int fr = 0) {
    FOR(i, 1, MAXK-1) {
        par[v][i] = par[par[v][i-1]][i-1];
        mx[v][i] = max(mx[v][i-1], mx[par[v][i-1]][i-1]);
    }

    for (auto pp : adj[v]) {
        int u = pp.f;
        int cnt = pp.s;
        if (u == p) continue;

        dep[u] = dep[v]+1;
        par[u][0] = v;
        mx[u][0] = cnt;

        longMaz[u] = longDid[u] = 1;
        if (cnt < fr) longDid[u] = longDid[v] + 1;
        else longMaz[u] = longMaz[v] + 1;

        dfs (u, v, cnt);
    }
}

int lift (int v, int d) {
    FOR(i, 0, MAXK-1)
        if (d & (1<<i))
            v = par[v][i];
    return v;
}

int lca (int u, int v) {
    if (u == v) return u;
    if (dep[u] < dep[v])swap(u,v);
    int d = dep[u] - dep[v];
    FOR(i, 0, MAXK-1)
        if (d & (1<<i))
            u = par[u][i];
    if (u == v) return u;

    for (int i = MAXK-1; i >= 0; i--) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }

    return par[u][0];
}

int getMx (int u, int v) {
    if (u == v) return 0;
    int ret = 0;
    if (dep[u] < dep[v])swap(u,v);
    int d = dep[u] - dep[v];
    FOR(i, 0, MAXK-1) {
        if (d & (1<<i)) {
            ret = max(ret, mx[u][i]);
            u = par[u][i];
        }
    }

    if (u == v) return ret;

    for (int i = MAXK-1; i >= 0; i--) {
        if (par[u][i] != par[v][i]) {
            ret = max(ret, mx[v][i]);
            ret = max(ret, mx[u][i]);
            u = par[u][i];
            v = par[v][i];
        }
    }

    ret = max(ret, mx[v][0]);
    ret = max(ret, mx[u][0]);

    return ret;
}

bool query (int a, int d, int t) {
    if (a == d) return true;
    if (getMx(a, d) > t) return false;

    swap(a,d);

    int anc = lca(a, d);
    //cout << " "
    if (longDid[a] >= dep[a]-dep[anc] && longMaz[d] >= dep[d]-dep[anc]) {
            //cout << " h  ere" << endl;
        int cnt1 = 0, cnt2 = 0;

        if (a == anc || d == anc) return true;

        int a1 = lift(a, dep[a]-dep[anc]-1);
        int d1 = lift(d, dep[d]-dep[anc]-1);

        cnt1 = mx[a1][0];
        cnt2 = mx[d1][0];

        //cout << " a= " << a << " d= " << d << " cnt1 = " << cnt1 << " cnt2 = " << cnt2 << endl;
        //cout << "  a1 = " << a1 << " d1 = " << d1 << endl;
        //cout << "  anc = " << anc << " depa = " << dep[a] << " depd= " << dep[d] << " depanc = " <<dep[anc] << endl;

        if (cnt1 < cnt2) return true;

        return false;
    }

    return false;
}

void share (int u, int v) {

}

int qCount (int d) {
    return 1;
}

int main()
{
    FAST_IO;

    cin >> n >> k;
    //FOR(i, 1, n) nodes[i].insert(i);
    //FOR(i, 1, n) cntN[i] ++;
    FOR(cnt, 1, n+k-1) {
        char c;
        cin >> c;
        int a, b = 0;
        if (c == 'S') cin >> a >> b;
        else if (c == 'Q') cin >> a >> b;
        else cin >> a;
        queries.pb({c, {a,b}});

        if (c == 'S') {
               // cnt++;
            adj[a].pb({b, cnt});
            adj[b].pb({a, cnt});
        }
    }

    dfs (1, -1 );

    int cnt = 0;
    for (auto q : queries) {
        cnt++;
        if (q.f == 'S') {
            share(q.s.f, q.s.s);
            continue;
        }

        if (q.f == 'Q') {
            if (query (q.s.f, q.s.s, cnt)) cout << "yes\n";
            else cout << "no\n";
        } else {
            cout << qCount(q.s.f) << "\n";
        }
    }

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14484 KB Output is correct
2 Correct 59 ms 16016 KB Output is correct
3 Correct 69 ms 16204 KB Output is correct
4 Correct 61 ms 16196 KB Output is correct
5 Correct 66 ms 16472 KB Output is correct
6 Correct 72 ms 16192 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14484 KB Output is correct
2 Correct 59 ms 16016 KB Output is correct
3 Correct 69 ms 16204 KB Output is correct
4 Correct 61 ms 16196 KB Output is correct
5 Correct 66 ms 16472 KB Output is correct
6 Correct 72 ms 16192 KB Output is correct
7 Incorrect 46 ms 14112 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 14468 KB Output is correct
2 Correct 199 ms 43044 KB Output is correct
3 Correct 191 ms 43120 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 14468 KB Output is correct
2 Correct 199 ms 43044 KB Output is correct
3 Correct 191 ms 43120 KB Output is correct
4 Incorrect 48 ms 14032 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14552 KB Output is correct
2 Correct 178 ms 53856 KB Output is correct
3 Correct 187 ms 53844 KB Output is correct
4 Correct 195 ms 53752 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14552 KB Output is correct
2 Correct 178 ms 53856 KB Output is correct
3 Correct 187 ms 53844 KB Output is correct
4 Correct 195 ms 53752 KB Output is correct
5 Incorrect 41 ms 14028 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14628 KB Output is correct
2 Correct 180 ms 43524 KB Output is correct
3 Correct 173 ms 43888 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14628 KB Output is correct
2 Correct 180 ms 43524 KB Output is correct
3 Correct 173 ms 43888 KB Output is correct
4 Incorrect 45 ms 14084 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14520 KB Output is correct
2 Correct 187 ms 54024 KB Output is correct
3 Correct 183 ms 53808 KB Output is correct
4 Correct 212 ms 53812 KB Output is correct
5 Correct 45 ms 14848 KB Output is correct
6 Correct 195 ms 43596 KB Output is correct
7 Correct 164 ms 43884 KB Output is correct
8 Correct 246 ms 44396 KB Output is correct
9 Correct 205 ms 44272 KB Output is correct
10 Correct 225 ms 49580 KB Output is correct
11 Correct 302 ms 48752 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14520 KB Output is correct
2 Correct 187 ms 54024 KB Output is correct
3 Correct 183 ms 53808 KB Output is correct
4 Correct 212 ms 53812 KB Output is correct
5 Correct 45 ms 14848 KB Output is correct
6 Correct 195 ms 43596 KB Output is correct
7 Correct 164 ms 43884 KB Output is correct
8 Correct 246 ms 44396 KB Output is correct
9 Correct 205 ms 44272 KB Output is correct
10 Correct 225 ms 49580 KB Output is correct
11 Correct 302 ms 48752 KB Output is correct
12 Incorrect 42 ms 14020 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14496 KB Output is correct
2 Correct 58 ms 16084 KB Output is correct
3 Correct 70 ms 16264 KB Output is correct
4 Correct 63 ms 16284 KB Output is correct
5 Correct 67 ms 16576 KB Output is correct
6 Correct 70 ms 16192 KB Output is correct
7 Correct 50 ms 14832 KB Output is correct
8 Correct 199 ms 42956 KB Output is correct
9 Correct 197 ms 43128 KB Output is correct
10 Correct 42 ms 14896 KB Output is correct
11 Correct 185 ms 53936 KB Output is correct
12 Correct 182 ms 53924 KB Output is correct
13 Correct 189 ms 53792 KB Output is correct
14 Correct 45 ms 14872 KB Output is correct
15 Correct 178 ms 43472 KB Output is correct
16 Correct 174 ms 43948 KB Output is correct
17 Correct 234 ms 44304 KB Output is correct
18 Correct 200 ms 44280 KB Output is correct
19 Correct 233 ms 49520 KB Output is correct
20 Correct 297 ms 48764 KB Output is correct
21 Correct 200 ms 43556 KB Output is correct
22 Correct 208 ms 43628 KB Output is correct
23 Correct 202 ms 43864 KB Output is correct
24 Correct 206 ms 44000 KB Output is correct
25 Correct 227 ms 46176 KB Output is correct
26 Correct 174 ms 43500 KB Output is correct
27 Correct 167 ms 43396 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14496 KB Output is correct
2 Correct 58 ms 16084 KB Output is correct
3 Correct 70 ms 16264 KB Output is correct
4 Correct 63 ms 16284 KB Output is correct
5 Correct 67 ms 16576 KB Output is correct
6 Correct 70 ms 16192 KB Output is correct
7 Correct 50 ms 14832 KB Output is correct
8 Correct 199 ms 42956 KB Output is correct
9 Correct 197 ms 43128 KB Output is correct
10 Correct 42 ms 14896 KB Output is correct
11 Correct 185 ms 53936 KB Output is correct
12 Correct 182 ms 53924 KB Output is correct
13 Correct 189 ms 53792 KB Output is correct
14 Correct 45 ms 14872 KB Output is correct
15 Correct 178 ms 43472 KB Output is correct
16 Correct 174 ms 43948 KB Output is correct
17 Correct 234 ms 44304 KB Output is correct
18 Correct 200 ms 44280 KB Output is correct
19 Correct 233 ms 49520 KB Output is correct
20 Correct 297 ms 48764 KB Output is correct
21 Correct 200 ms 43556 KB Output is correct
22 Correct 208 ms 43628 KB Output is correct
23 Correct 202 ms 43864 KB Output is correct
24 Correct 206 ms 44000 KB Output is correct
25 Correct 227 ms 46176 KB Output is correct
26 Correct 174 ms 43500 KB Output is correct
27 Correct 167 ms 43396 KB Output is correct
28 Incorrect 45 ms 14116 KB Extra information in the output file
29 Halted 0 ms 0 KB -