oj.uz

Submission #399152

# Submission time Handle Problem Language Result Execution time Memory
399152 2021-05-05T11:06:33 Z egekabas Inside information (BOI21_servers) C++14
2.5 / 100
 221 ms 57760 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n, k;

char t[240009];
int x[240009];
int y[240009];

vector<pii> g[120009];

int dad[120009][25];
int depth[120009];

int pval[120009][25];
int incr[120009][25];
int decr[120009][25];

void dfs(int v, int prt){
    dad[v][0] = prt;
    depth[v] = depth[prt]+1;

    for(int i = 1; i < 25; ++i){
        dad[v][i] = dad[dad[v][i-1]][i-1];
        pval[v][i] = pval[dad[v][i-1]][i-1];
        if(incr[v][i-1] && incr[dad[v][i-1]][i-1] && pval[v][i-1] < pval[dad[v][i-1]][0])
            incr[v][i] = 1;
        if(decr[v][i-1] && decr[dad[v][i-1]][i-1] && pval[v][i-1] > pval[dad[v][i-1]][0])
            decr[v][i] = 1;
    }
    for(auto u : g[v])
        if(u.ff != prt){
            incr[u.ff][0] = decr[u.ff][0] = 1;
            pval[u.ff][0] = u.ss;
            dfs(u.ff, v);
        }
}
int lca(int x, int y){
    if(depth[y] > depth[x])
        swap(x, y);
    for(int i = 24; i >= 0; --i)
        if(depth[dad[x][i]] >= depth[y])
            x = dad[x][i];
    if(x == y) return x;
    for(int i = 24; i >= 0; --i)
        if(dad[x][i] != dad[y][i]){
            x = dad[x][i];
            y = dad[y][i];
        }
    return dad[x][0];
}
struct retst{
    int incr = 1, decr = 1, maxi = -1, last = -1;
};
retst goup(int x, int y){
    retst ret;
    for(int i = 24; i >= 0; --i)
        if(depth[dad[x][i]] >= depth[y]){
            if(ret.last != -1 && ret.last > pval[x][0])
                ret.incr = 0;
            if(ret.last != -1 && ret.last < pval[x][0])
                ret.decr = 0;
            ret.maxi = max({ret.maxi, pval[x][0], pval[x][i]});
            ret.last = pval[x][i];
            x = dad[x][i];
        }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> k;
    for(int i = 0; i < n+k-1; ++i){
        cin >> t[i];
        if(t[i] == 'C')
            cin >> x[i];
        else
            cin >> x[i] >> y[i];
        if(t[i] == 'S'){
            g[x[i]].pb({y[i], i});
            g[y[i]].pb({x[i], i});
        }
    }
    dfs(1, 0);
    int outsz = 0;
    for(int i = 0; i < n+k-1; ++i){
        if(t[i] == 'S') continue;
        else if(t[i] == 'Q'){
            int lc = lca(x[i], y[i]);
            retst a = goup(x[i], lc);
            retst b = goup(y[i], lc);
            if(a.decr && b.incr && (a.last == -1 || b.last == -1 || a.last > b.last) && max(a.maxi, b.maxi) <= i){
                cout << "yes\n";
                outsz++;
            }
            else{
                cout << "no\n";
                outsz++;
            }
        }
        else{
            cout << "0\n";
            outsz++;
        }
        assert(outsz <= k);
    }
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 4536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 4536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4640 KB Output is correct
2 Correct 207 ms 57692 KB Output is correct
3 Correct 221 ms 57760 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4640 KB Output is correct
2 Correct 207 ms 57692 KB Output is correct
3 Correct 221 ms 57760 KB Output is correct
4 Incorrect 61 ms 4608 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 4596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 4596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 4736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 4736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 4512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 4512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 4548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 4548 KB Output isn't correct
2 Halted 0 ms 0 KB -