oj.uz

Submission #405554

# Submission time Handle Problem Language Result Execution time Memory
405554 2021-05-16T14:24:15 Z ernest0_0abreu Inside information (BOI21_servers) C++17
30 / 100
 3500 ms 55616 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 59 ms 9272 KB Output is correct
2 Correct 69 ms 11800 KB Output is correct
3 Correct 70 ms 11828 KB Output is correct
4 Correct 89 ms 11864 KB Output is correct
5 Correct 87 ms 12112 KB Output is correct
6 Correct 98 ms 11852 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9272 KB Output is correct
2 Correct 69 ms 11800 KB Output is correct
3 Correct 70 ms 11828 KB Output is correct
4 Correct 89 ms 11864 KB Output is correct
5 Correct 87 ms 12112 KB Output is correct
6 Correct 98 ms 11852 KB Output is correct
7 Incorrect 64 ms 9364 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 56 ms 9376 KB Output is correct
2 Execution timed out 3559 ms 45956 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 9376 KB Output is correct
2 Execution timed out 3559 ms 45956 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9292 KB Output is correct
2 Correct 231 ms 55572 KB Output is correct
3 Correct 235 ms 55616 KB Output is correct
4 Correct 255 ms 55392 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9292 KB Output is correct
2 Correct 231 ms 55572 KB Output is correct
3 Correct 235 ms 55616 KB Output is correct
4 Correct 255 ms 55392 KB Output is correct
5 Incorrect 67 ms 9392 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 53 ms 9336 KB Output is correct
2 Correct 217 ms 47040 KB Output is correct
3 Correct 234 ms 47484 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 9336 KB Output is correct
2 Correct 217 ms 47040 KB Output is correct
3 Correct 234 ms 47484 KB Output is correct
4 Incorrect 59 ms 9448 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 59 ms 9212 KB Output is correct
2 Correct 230 ms 55516 KB Output is correct
3 Correct 232 ms 55536 KB Output is correct
4 Correct 260 ms 55444 KB Output is correct
5 Correct 54 ms 10164 KB Output is correct
6 Correct 215 ms 47204 KB Output is correct
7 Correct 236 ms 47660 KB Output is correct
8 Correct 290 ms 47856 KB Output is correct
9 Correct 269 ms 47896 KB Output is correct
10 Correct 319 ms 52544 KB Output is correct
11 Correct 392 ms 51716 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9212 KB Output is correct
2 Correct 230 ms 55516 KB Output is correct
3 Correct 232 ms 55536 KB Output is correct
4 Correct 260 ms 55444 KB Output is correct
5 Correct 54 ms 10164 KB Output is correct
6 Correct 215 ms 47204 KB Output is correct
7 Correct 236 ms 47660 KB Output is correct
8 Correct 290 ms 47856 KB Output is correct
9 Correct 269 ms 47896 KB Output is correct
10 Correct 319 ms 52544 KB Output is correct
11 Correct 392 ms 51716 KB Output is correct
12 Incorrect 64 ms 9404 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 60 ms 9348 KB Output is correct
2 Correct 69 ms 11828 KB Output is correct
3 Correct 70 ms 11840 KB Output is correct
4 Correct 88 ms 11832 KB Output is correct
5 Correct 85 ms 12068 KB Output is correct
6 Correct 97 ms 11772 KB Output is correct
7 Correct 58 ms 10208 KB Output is correct
8 Execution timed out 3552 ms 46056 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 9348 KB Output is correct
2 Correct 69 ms 11828 KB Output is correct
3 Correct 70 ms 11840 KB Output is correct
4 Correct 88 ms 11832 KB Output is correct
5 Correct 85 ms 12068 KB Output is correct
6 Correct 97 ms 11772 KB Output is correct
7 Correct 58 ms 10208 KB Output is correct
8 Execution timed out 3552 ms 46056 KB Time limit exceeded
9 Halted 0 ms 0 KB -