oj.uz

Submission #400914

# Submission time Handle Problem Language Result Execution time Memory
400914 2021-05-08T20:03:34 Z 534351 Inside information (BOI21_servers) C++17
50 / 100
 261 ms 61532 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

const int MAXN = 240013;
const int INF = 1e9 + 7;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, K, T;
int parent[MAXN], subtree[MAXN], st[MAXN], ft[MAXN], dup[MAXN];
int ancestor[20][MAXN];
bool incr[20][MAXN], decr[20][MAXN];
int mx[20][MAXN], mn[20][MAXN];
vpi edge[MAXN];
pair<int, pii> quer[MAXN];

bool insubt(int u, int v) //is v in the subtree of u?
{
    return (u == N || (st[u] <= st[v] && st[v] <= ft[u]));
}
void dfs(int u, int p)
{
    st[u] = T;
    ft[u] = T;
    T++;
    subtree[u] = 1;
    for (auto e : edge[u])
    {
        int v = e.fi, d = e.se;
        if (v == p) continue;
        parent[v] = u;
        dup[v] = d;
        dfs(v, u);
        subtree[u] += subtree[v];
        ft[u] = ft[v];
    }
}
bool check(int u, int v, int t)
{
    //return if v -> u is stirctl increasing and max is <= t
    // cerr << "Check " << v << " -> " << u << endl;
    int curmx = -1;
    int w = v;
    //v going up, so it has to keep on increasing
    FORD(i, 20, 0)
    {
        if (!insubt(ancestor[i][w], u))
        {
            if (mn[i][w] < curmx || !incr[i][w] || mx[i][w] > t) return false;
            curmx = mx[i][w];
            w = ancestor[i][w];
        }
    }
    if (!insubt(w, u))
    {
        if (mn[0][w] < curmx || mx[0][w] > t) return false;
        curmx = mx[0][w];
    }
    //u going up, so it has to keep on decreasing.
    w = u;
    int curmn = INF;
    FORD(i, 20, 0)
    {
        if (!insubt(ancestor[i][w], v))
        {
            if (mx[i][w] > curmn || !decr[i][w] || mx[i][w] > t) return false;
            curmn = mn[i][w];
            w = ancestor[i][w];
        }
    }
    if (!insubt(w, v))
    {
        if (mx[0][w] > curmn || mx[0][w] > t) return false;
        curmn = mn[0][w];
    }
    if (curmn < curmx)
    {
        return false;
    }
    return true;
}

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> K;
    FOR(i, 0, N + K - 1)
    {
        char qid; cin >> qid;
        if (qid == 'S')
        {
            int u, v;
            cin >> u >> v; u--; v--;
            quer[i] = {0, {u, v}};
            edge[u].PB({v, i});
            edge[v].PB({u, i});
        }
        if (qid == 'Q')
        {
            int u, v;
            cin >> u >> v; u--; v--;
            quer[i] = {1, {u, v}};
            // cout << (get(u) == get(v) ? "yes" : "no") << '\n';
        }
        if (qid == 'C')
        {
            int u;
            cin >> u; u--;
            quer[i] = {2, {u, -1}};
            // cout << siz[get(u)] << '\n';
        }
    }
    parent[0] = N; parent[N] = N;
    dfs(0, N);
    FOR(i, 0, N + 1)
    {
        ancestor[0][i] = parent[i];
        mx[0][i] = dup[i];
        mn[0][i] = dup[i];
        incr[0][i] = true;
        decr[0][i] = true;
    }
    FOR(i, 1, 20)
    {
        FOR(j, 0, N + 1)
        {
            int k = ancestor[i - 1][j];
            ancestor[i][j] = ancestor[i - 1][k];
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][k]);
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][k]);
            incr[i][j] = (incr[i - 1][j] && incr[i - 1][k] && mx[i - 1][j] < mn[i - 1][k]);
            decr[i][j] = (decr[i - 1][j] && decr[i - 1][k] && mn[i - 1][j] > mx[i - 1][k]);
        }
    }
    FOR(i, 0, N + K - 1)
    {
        if (quer[i].fi == 1)
        {
            int u = quer[i].se.fi, v = quer[i].se.se;
            cout << ((u == v || check(u, v, i)) ? "yes" : "no") << '\n';
            //check if v -> u is strictly increasing.
        }
        if (quer[i].fi == 2)
        {
            cout << "69\n";
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8236 KB Output is correct
2 Correct 49 ms 9540 KB Output is correct
3 Correct 55 ms 9612 KB Output is correct
4 Correct 51 ms 9724 KB Output is correct
5 Correct 58 ms 9904 KB Output is correct
6 Correct 58 ms 9572 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8236 KB Output is correct
2 Correct 49 ms 9540 KB Output is correct
3 Correct 55 ms 9612 KB Output is correct
4 Correct 51 ms 9724 KB Output is correct
5 Correct 58 ms 9904 KB Output is correct
6 Correct 58 ms 9572 KB Output is correct
7 Incorrect 57 ms 8276 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 45 ms 8300 KB Output is correct
2 Correct 184 ms 49672 KB Output is correct
3 Correct 179 ms 49576 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 8300 KB Output is correct
2 Correct 184 ms 49672 KB Output is correct
3 Correct 179 ms 49576 KB Output is correct
4 Incorrect 42 ms 8228 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 8260 KB Output is correct
2 Correct 223 ms 58064 KB Output is correct
3 Correct 188 ms 61328 KB Output is correct
4 Correct 187 ms 61272 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8260 KB Output is correct
2 Correct 223 ms 58064 KB Output is correct
3 Correct 188 ms 61328 KB Output is correct
4 Correct 187 ms 61272 KB Output is correct
5 Incorrect 42 ms 9056 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 41 ms 8288 KB Output is correct
2 Correct 151 ms 49544 KB Output is correct
3 Correct 180 ms 49996 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8288 KB Output is correct
2 Correct 151 ms 49544 KB Output is correct
3 Correct 180 ms 49996 KB Output is correct
4 Incorrect 40 ms 8220 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 42 ms 8472 KB Output is correct
2 Correct 194 ms 58068 KB Output is correct
3 Correct 188 ms 61380 KB Output is correct
4 Correct 185 ms 61532 KB Output is correct
5 Correct 41 ms 9172 KB Output is correct
6 Correct 152 ms 52812 KB Output is correct
7 Correct 182 ms 53308 KB Output is correct
8 Correct 196 ms 53748 KB Output is correct
9 Correct 197 ms 53740 KB Output is correct
10 Correct 226 ms 58180 KB Output is correct
11 Correct 251 ms 57540 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8472 KB Output is correct
2 Correct 194 ms 58068 KB Output is correct
3 Correct 188 ms 61380 KB Output is correct
4 Correct 185 ms 61532 KB Output is correct
5 Correct 41 ms 9172 KB Output is correct
6 Correct 152 ms 52812 KB Output is correct
7 Correct 182 ms 53308 KB Output is correct
8 Correct 196 ms 53748 KB Output is correct
9 Correct 197 ms 53740 KB Output is correct
10 Correct 226 ms 58180 KB Output is correct
11 Correct 251 ms 57540 KB Output is correct
12 Incorrect 42 ms 9072 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 43 ms 8240 KB Output is correct
2 Correct 49 ms 9600 KB Output is correct
3 Correct 55 ms 9604 KB Output is correct
4 Correct 51 ms 9668 KB Output is correct
5 Correct 54 ms 9820 KB Output is correct
6 Correct 59 ms 9688 KB Output is correct
7 Correct 44 ms 8308 KB Output is correct
8 Correct 175 ms 49568 KB Output is correct
9 Correct 174 ms 49588 KB Output is correct
10 Correct 42 ms 8264 KB Output is correct
11 Correct 192 ms 57980 KB Output is correct
12 Correct 186 ms 61360 KB Output is correct
13 Correct 182 ms 61284 KB Output is correct
14 Correct 42 ms 9128 KB Output is correct
15 Correct 154 ms 52880 KB Output is correct
16 Correct 180 ms 53316 KB Output is correct
17 Correct 171 ms 53684 KB Output is correct
18 Correct 210 ms 53880 KB Output is correct
19 Correct 220 ms 58164 KB Output is correct
20 Correct 261 ms 57540 KB Output is correct
21 Correct 194 ms 52940 KB Output is correct
22 Correct 193 ms 52952 KB Output is correct
23 Correct 198 ms 53232 KB Output is correct
24 Correct 212 ms 53280 KB Output is correct
25 Correct 241 ms 55028 KB Output is correct
26 Correct 184 ms 52804 KB Output is correct
27 Correct 156 ms 52816 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8240 KB Output is correct
2 Correct 49 ms 9600 KB Output is correct
3 Correct 55 ms 9604 KB Output is correct
4 Correct 51 ms 9668 KB Output is correct
5 Correct 54 ms 9820 KB Output is correct
6 Correct 59 ms 9688 KB Output is correct
7 Correct 44 ms 8308 KB Output is correct
8 Correct 175 ms 49568 KB Output is correct
9 Correct 174 ms 49588 KB Output is correct
10 Correct 42 ms 8264 KB Output is correct
11 Correct 192 ms 57980 KB Output is correct
12 Correct 186 ms 61360 KB Output is correct
13 Correct 182 ms 61284 KB Output is correct
14 Correct 42 ms 9128 KB Output is correct
15 Correct 154 ms 52880 KB Output is correct
16 Correct 180 ms 53316 KB Output is correct
17 Correct 171 ms 53684 KB Output is correct
18 Correct 210 ms 53880 KB Output is correct
19 Correct 220 ms 58164 KB Output is correct
20 Correct 261 ms 57540 KB Output is correct
21 Correct 194 ms 52940 KB Output is correct
22 Correct 193 ms 52952 KB Output is correct
23 Correct 198 ms 53232 KB Output is correct
24 Correct 212 ms 53280 KB Output is correct
25 Correct 241 ms 55028 KB Output is correct
26 Correct 184 ms 52804 KB Output is correct
27 Correct 156 ms 52816 KB Output is correct
28 Incorrect 41 ms 9100 KB Extra information in the output file
29 Halted 0 ms 0 KB -