oj.uz

Submission #405580

# Submission time Handle Problem Language Result Execution time Memory
405580 2021-05-16T14:44:51 Z ernest0_0abreu Inside information (BOI21_servers) C++17
30 / 100
 3500 ms 52352 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5, INF = 2e9;
vector<pair<int,int>> g[MAXN], C;
vector<pair<int,pair<int,int>>> Q;
vector<pair<int,pair<char,int>>> ansv;

int lcaM[MAXN][20], lca[MAXN][20], lcaC[MAXN][20];
int lvl[MAXN];
int dp[MAXN], dpEdge[MAXN][2];

    void dfs(int u, int p, int lastedge){
        for(auto x : g[u]){
            int v = x.first, w = x.second;
            if(v != p){
                lca[v][0] = u;
                lcaM[v][0] = w;
                if(w > lastedge)
                    lcaC[v][0] = 1;
                lvl[v] = lvl[u] + 1;
                dfs(v , u , w);
            }
        }
    }

    pair<int,int> LCA(int a, int b){
        int _lca, _max = 0;

        if(lvl[a] > lvl[b]) swap(a,b);
        for(int i = 19; i >= 0; --i){
            if(lvl[lca[b][i]] >= lvl[a]){
                _max = max(_max , lcaM[b][i]);
                b = lca[b][i];
            }
        }
        for(int i = 19; i >= 0; --i){
            if(lca[a][i] != lca[b][i]){
                _max = max(_max , lcaM[a][i]);
                _max = max(_max , lcaM[b][i]);
                a = lca[a][i];
                b = lca[b][i];
            }
        }
        // cerr << a << ' ' << b << '\n';

        if(a != b){
            _max = max(_max , lcaM[a][0]);
            _max = max(_max , lcaM[b][0]);
            _lca = lca[a][0];
        }
        else _lca = a;

        return {_lca , _max};
    }

    bool Check(int a, int b, int _lca){

        if(a == b) return true;


        int cost = 0;
        for(int i = 19; i >= 0; --i){
            if(lvl[lca[a][i]] > lvl[_lca]){
                cost += lcaC[a][i];
                a = lca[a][i];
            }
        }
        if(cost) 
            return false;

        cost = 0; int original_b = b;
        for(int i = 19; i >= 0; --i){
            if(lvl[lca[b][i]] > lvl[_lca]){
                cost += lcaC[b][i];
                b = lca[b][i];
            }
        }

        if(cost != lvl[original_b] - lvl[b]) 
            return false;

        if(a == _lca || b == _lca)
            return true;
        
        if(lcaM[a][0] < lcaM[b][0])
            return true;

        return false;
    }

    int DPEdge(int u, int id, int dir){
        if(dpEdge[id][dir] != -1)  return dpEdge[id][dir];
        dpEdge[id][dir] = 1;
        for(auto x : g[u]){
            int v = x.first, w = x.second;
            if(id == w) continue;
            if(w > id)
                dpEdge[id][dir] += DPEdge(v , w , (u < v));
        }
        return dpEdge[id][dir];
    }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    for(int i = 1; i < n+q; ++i){
        char c;
        cin >> c;
        if(c == 'S'){
            int u, v;
            cin >> u >> v;
            g[u].push_back({v,i});
            g[v].push_back({u,i});
        }   
        if(c == 'Q'){ 
            int a, b;
            cin >> a >> b;
            Q.push_back({i , {a,b}});
        }
        if(c == 'C'){
            int x;
            cin >> x;
            C.push_back({i,x});
        }
    }

{   //Subproblem for Query 'Q'
    lvl[1] = 1;
    dfs(1 , 0 , INF);

    for(int k = 1; k < 20; ++k)
        for(int i = 1; i <= n; ++i){
            lca[i][k] = lca[lca[i][k-1]][k-1];
            lcaM[i][k] = max(lcaM[i][k-1] , lcaM[lca[i][k-1]][k-1]);
            lcaC[i][k] = lcaC[i][k-1] + lcaC[lca[i][k-1]][k-1];
        }

    for(auto x : Q){
        int a, b, w;
        a = x.second.first, b = x.second.second;
        w = x.first;

        pair<int,int> p = LCA(a , b);
        int _lca = p.first, _max = p.second;

        // cerr << _lca << '\n';
        bool ans = Check(b , a, _lca);

        if(_max > w)
            ans = false;

        if(ans)
            ansv.push_back({w , {'Q' , 1}});
        else
            ansv.push_back({w , {'Q' , 0}});
    }
}
    
    for(int i = 1; i < n+q; ++i)
        dpEdge[i][0] = dpEdge[i][1] = -1;

    for(int i = 1; i <= n; ++i)
        for(auto x : g[i]){
            int v = x.first, w = x.second;
            dp[i] += DPEdge(v , w , (i < v));
        }

    for(auto x : C)
        ansv.push_back({x.first , {'C' , dp[x.second] + 1}});

    sort(ansv.begin() , ansv.end());

    for(auto x : ansv){
        if(x.second.first == 'Q'){
            if(x.second.second)
                cout << "yes\n";
            else
                cout << "no\n";
        }
        else
            cout << x.second.second << '\n';
    }

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9216 KB Output is correct
2 Correct 67 ms 10408 KB Output is correct
3 Correct 70 ms 10456 KB Output is correct
4 Correct 98 ms 10676 KB Output is correct
5 Correct 90 ms 10668 KB Output is correct
6 Correct 98 ms 10520 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9216 KB Output is correct
2 Correct 67 ms 10408 KB Output is correct
3 Correct 70 ms 10456 KB Output is correct
4 Correct 98 ms 10676 KB Output is correct
5 Correct 90 ms 10668 KB Output is correct
6 Correct 98 ms 10520 KB Output is correct
7 Incorrect 64 ms 9296 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 9248 KB Output is correct
2 Execution timed out 3565 ms 43272 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 9248 KB Output is correct
2 Execution timed out 3565 ms 43272 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 9228 KB Output is correct
2 Correct 240 ms 52152 KB Output is correct
3 Correct 241 ms 52352 KB Output is correct
4 Correct 262 ms 52160 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 9228 KB Output is correct
2 Correct 240 ms 52152 KB Output is correct
3 Correct 241 ms 52352 KB Output is correct
4 Correct 262 ms 52160 KB Output is correct
5 Incorrect 64 ms 9312 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 54 ms 9228 KB Output is correct
2 Correct 213 ms 43684 KB Output is correct
3 Correct 246 ms 44180 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9228 KB Output is correct
2 Correct 213 ms 43684 KB Output is correct
3 Correct 246 ms 44180 KB Output is correct
4 Incorrect 66 ms 9316 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 61 ms 9272 KB Output is correct
2 Correct 240 ms 52164 KB Output is correct
3 Correct 222 ms 52168 KB Output is correct
4 Correct 257 ms 52204 KB Output is correct
5 Correct 53 ms 9272 KB Output is correct
6 Correct 216 ms 43736 KB Output is correct
7 Correct 229 ms 44276 KB Output is correct
8 Correct 294 ms 44632 KB Output is correct
9 Correct 257 ms 44664 KB Output is correct
10 Correct 301 ms 49108 KB Output is correct
11 Correct 385 ms 48388 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 9272 KB Output is correct
2 Correct 240 ms 52164 KB Output is correct
3 Correct 222 ms 52168 KB Output is correct
4 Correct 257 ms 52204 KB Output is correct
5 Correct 53 ms 9272 KB Output is correct
6 Correct 216 ms 43736 KB Output is correct
7 Correct 229 ms 44276 KB Output is correct
8 Correct 294 ms 44632 KB Output is correct
9 Correct 257 ms 44664 KB Output is correct
10 Correct 301 ms 49108 KB Output is correct
11 Correct 385 ms 48388 KB Output is correct
12 Incorrect 63 ms 9320 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 9288 KB Output is correct
2 Correct 69 ms 10404 KB Output is correct
3 Correct 70 ms 10504 KB Output is correct
4 Correct 87 ms 10528 KB Output is correct
5 Correct 84 ms 10752 KB Output is correct
6 Correct 95 ms 10456 KB Output is correct
7 Correct 55 ms 9296 KB Output is correct
8 Execution timed out 3567 ms 43108 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 9288 KB Output is correct
2 Correct 69 ms 10404 KB Output is correct
3 Correct 70 ms 10504 KB Output is correct
4 Correct 87 ms 10528 KB Output is correct
5 Correct 84 ms 10752 KB Output is correct
6 Correct 95 ms 10456 KB Output is correct
7 Correct 55 ms 9296 KB Output is correct
8 Execution timed out 3567 ms 43108 KB Time limit exceeded
9 Halted 0 ms 0 KB -