Submission #1064404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064404		not_amir	Inside information (BOI21_servers)	C++14	0 / 100	20 ms	3132 KiB

servers

#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) : m(m), M(M), d(d) {}

    edge operator+(edge const& other){
        if(d == '0')
            return other;
        if(other.d == '0')
            return d;
        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";
        }
    }
}

Compilation message (stderr)

servers.cpp: In function 'int dfs(int, int)':
servers.cpp:14:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto [u, w] : G[v]){
      |              ^
servers.cpp: In function 'int centroid(int, int, int)':
servers.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |     for(auto [u, w] : G[v]){
      |              ^
servers.cpp: In constructor 'edge::edge(int, int, char)':
servers.cpp:36:12: warning: 'edge::M' will be initialized after [-Wreorder]
   36 |     int m, M;
      |            ^
servers.cpp:35:10: warning:   'char edge::d' [-Wreorder]
   35 |     char d;
      |          ^
servers.cpp:40:5: warning:   when initialized here [-Wreorder]
   40 |     edge(int m, int M, char d) : m(m), M(M), d(d) {}
      |     ^~~~
servers.cpp: In function 'void dfs2(int, int, edge, int)':
servers.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for(auto [u, w] : G[v]){
      |              ^
servers.cpp: In function 'int centroid_decomp(int, int, int)':
servers.cpp:94:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |     for(auto [u, w] : G[centr]){
      |              ^
servers.cpp: In function 'int main()':
servers.cpp:135:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  135 |     for(auto [t, q] : Q){
      |              ^

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5