oj.uz

Submission #1064415

# Submission time Handle Problem Language Result Execution time Memory
1064415 2024-08-18T12:22:11 Z not_amir Inside information (BOI21_servers) C++17
2.5 / 100
 171 ms 34508 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define INF 1e9

vector<vector<pii>> G;
vector<bool> removed;
vector<int> S;

int dfs(int v, int p){
    S[v] = 1;
    for(auto [u, w] : G[v]){
        if(u == p || removed[u]) continue;
        S[v] += dfs(u, v);
    }
    return S[v];
}

stack<int> weights;

int centroid(int v, int n, int p){
    for(auto [u, w] : G[v]){
        if(u == p || removed[u]) continue;
        if(2 * S[u] > n){
            weights.push(w);
            return centroid(u, n, v);
        }
    }
    return v;
}

struct edge{
    char d;
    int m, M;

    edge(char c = '0') : d(c) {}
    edge(int w) : d('1'), m(w), M(w) {}
    edge(int m, int M, char d) : d(d), m(m), M(M) {}

    edge operator+(edge const& other){
        if(d == '0')
            return other;
        if(other.d == '0')
            return *this;
        if(d == '?' || other.d == '?')
            return edge('?');
        if(d == 'U' && other.d == 'D')
            return edge('?');
        if(d == 'D' && other.d == 'U')
            return edge('?');
        if(d == '1' && other.d == '1'){
            if (m < other.m)
                return edge(m, other.m, 'U');
            else
                return edge(other.m, m, 'D');
        }
        if(d == '1'){
            if(other.d == 'U' && M < other.m)
                return edge(m, other.M, 'U');
            if(other.d == 'D' && m > other.M)
                return edge(other.m, M, 'D');
        }
        if(d == 'U')
            if(M < other.m)
                return edge(m, other.M, 'U');
        if(d == 'D')
            if(m > other.M)
                return edge(other.m, M, 'U');
        return edge('?');
    }
};

vector<map<int, edge>> mp;
vector<set<int>> asdfgsa;
vector<int> parent, depth;

void dfs2(int v, int p, edge e, int centr){
    mp[centr][v] = e;
    for(auto [u, w] : G[v]){
        if(u == p || removed[u]) continue;
        dfs2(u, v, e + edge(w), centr);
    }
}

int centroid_decomp(int v, int p, int d = 0){
    int centr = centroid(v, dfs(v, p), p);

    depth[centr] = d;
    removed[centr] = 1;
    dfs2(centr, 0, edge(), centr);

    for(auto [u, w] : G[centr]){
        if(u == p || removed[u]) continue;
        parent[centroid_decomp(u, centr, d + 1)] = centr;
    }

    return centr;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    G.resize(n + 1);
    S.resize(n + 1);
    mp.resize(n + 1);
    removed.resize(n + 1);
    depth.resize(n + 1);
    parent.resize(n + 1);
    vector<pair<int, pii>> Q;
    Q.reserve(k);
    for(int i = 0; i < n + k - 1; i++){
        char c;
        cin >> c;
        if(c == 'S'){
            int a, b;
            cin >> a >> b;
            G[a].push_back({b, i});
            G[b].push_back({a, i});
        }
        if(c == 'Q'){
            int a, d;
            cin >> a >> d;
            Q.push_back({i, {a, d}});
        }
        if(c == 'C'){
            int d;
            cin >> d;
            Q.push_back({i, {-1, d}});
        }
    }
    centroid_decomp(1, 0);
    for(auto [t, q] : Q){
        int a = q.first, d = q.second;
        if(a == -1){
            cout << "1\n";
        }
        else{
            if(a == d){
                cout << "yes\n";
                continue;
            }
            int _a = a, _d = d;
            if(depth[_a] < depth[_d])
                swap(_a, _d);
            while(depth[_a] != depth[_d])
                _a = parent[_a];
            while(_a != _d){
                _a = parent[_a];
                _d = parent[_d];
            }
            edge e1 = mp[_a][d];
            if(e1.d == 'U')
                e1.d = 'D';
            else if(e1.d == 'D')
                e1.d = 'U';
            edge e = e1 + mp[_a][a];
            if((e.d == 'U' || e.d == '1') && e.M < t)
                cout << "yes\n";
            else
                cout << "no\n";
        }
    }
}

Subtask #1
0 / 2.5

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

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2144 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 19 ms 2140 KB Output is correct
2 Correct 160 ms 34504 KB Output is correct
3 Correct 171 ms 34508 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2140 KB Output is correct
2 Correct 160 ms 34504 KB Output is correct
3 Correct 171 ms 34508 KB Output is correct
4 Incorrect 18 ms 2908 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 23 ms 2140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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