oj.uz

Submission #405565

# Submission time Handle Problem Language Result Execution time Memory
405565 2021-05-16T14:34:13 Z ernest0_0abreu Inside information (BOI21_servers) C++17
30 / 100
 3500 ms 52316 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;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:177:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  177 |         if(x.second.first == 'Q')
      |           ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 9268 KB Output is correct
2 Correct 64 ms 10348 KB Output is correct
3 Correct 67 ms 10416 KB Output is correct
4 Correct 87 ms 10568 KB Output is correct
5 Correct 84 ms 10664 KB Output is correct
6 Correct 100 ms 10388 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 9268 KB Output is correct
2 Correct 64 ms 10348 KB Output is correct
3 Correct 67 ms 10416 KB Output is correct
4 Correct 87 ms 10568 KB Output is correct
5 Correct 84 ms 10664 KB Output is correct
6 Correct 100 ms 10388 KB Output is correct
7 Incorrect 59 ms 9316 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 54 ms 9296 KB Output is correct
2 Execution timed out 3562 ms 43100 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9296 KB Output is correct
2 Execution timed out 3562 ms 43100 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9292 KB Output is correct
2 Correct 249 ms 52264 KB Output is correct
3 Correct 247 ms 52216 KB Output is correct
4 Correct 279 ms 52132 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9292 KB Output is correct
2 Correct 249 ms 52264 KB Output is correct
3 Correct 247 ms 52216 KB Output is correct
4 Correct 279 ms 52132 KB Output is correct
5 Incorrect 64 ms 9232 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 55 ms 9296 KB Output is correct
2 Correct 221 ms 43704 KB Output is correct
3 Correct 232 ms 44272 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 9296 KB Output is correct
2 Correct 221 ms 43704 KB Output is correct
3 Correct 232 ms 44272 KB Output is correct
4 Incorrect 56 ms 9412 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 66 ms 9272 KB Output is correct
2 Correct 273 ms 52196 KB Output is correct
3 Correct 254 ms 52316 KB Output is correct
4 Correct 294 ms 52204 KB Output is correct
5 Correct 63 ms 9272 KB Output is correct
6 Correct 211 ms 43704 KB Output is correct
7 Correct 239 ms 44240 KB Output is correct
8 Correct 317 ms 44556 KB Output is correct
9 Correct 288 ms 44596 KB Output is correct
10 Correct 305 ms 49188 KB Output is correct
11 Correct 385 ms 48428 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 9272 KB Output is correct
2 Correct 273 ms 52196 KB Output is correct
3 Correct 254 ms 52316 KB Output is correct
4 Correct 294 ms 52204 KB Output is correct
5 Correct 63 ms 9272 KB Output is correct
6 Correct 211 ms 43704 KB Output is correct
7 Correct 239 ms 44240 KB Output is correct
8 Correct 317 ms 44556 KB Output is correct
9 Correct 288 ms 44596 KB Output is correct
10 Correct 305 ms 49188 KB Output is correct
11 Correct 385 ms 48428 KB Output is correct
12 Incorrect 60 ms 9324 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 57 ms 9316 KB Output is correct
2 Correct 65 ms 10356 KB Output is correct
3 Correct 68 ms 10472 KB Output is correct
4 Correct 86 ms 10528 KB Output is correct
5 Correct 83 ms 10792 KB Output is correct
6 Correct 103 ms 10452 KB Output is correct
7 Correct 54 ms 9248 KB Output is correct
8 Execution timed out 3569 ms 43140 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 9316 KB Output is correct
2 Correct 65 ms 10356 KB Output is correct
3 Correct 68 ms 10472 KB Output is correct
4 Correct 86 ms 10528 KB Output is correct
5 Correct 83 ms 10792 KB Output is correct
6 Correct 103 ms 10452 KB Output is correct
7 Correct 54 ms 9248 KB Output is correct
8 Execution timed out 3569 ms 43140 KB Time limit exceeded
9 Halted 0 ms 0 KB -