oj.uz

Submission #1001749

# Submission time Handle Problem Language Result Execution time Memory
1001749 2024-06-19T07:29:22 Z amine_aroua Inside information (BOI21_servers) C++17
2.5 / 100
 316 ms 57724 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int MAXN=3e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
bool removed[MAXN];
int join[20][MAXN];
vector<pair<int,int>> cnt[MAXN];
vector<pair<int,int>> adj[MAXN];
int sz[MAXN];
int up[20][MAXN];
int parent[20][MAXN];
int belongs[20][MAXN];
int get_sz(int x,int p){
    sz[x]=1;
    for(auto u:adj[x]){
        if(removed[u.fi]||u.fi==p) continue;
        sz[x]+=get_sz(u.fi,x);
    }
    return sz[x];
}
int get_centroid(int x,int t_sz,int p){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        if(sz[u.fi]*2>t_sz) return get_centroid(u.fi,t_sz,x);
    }
    return x;
}
bool incre[20][MAXN] , decre[20][MAXN];
int cur;
void dfs(int x,int p,int edgep,int centroid,int lvl,int edge , int node){
    cur++;
    belongs[lvl][x] = node;
    if(incre[lvl][x]) join[lvl][x] = edge;
    if(decre[lvl][x]) up[lvl][x] = edgep;
    parent[lvl][x] = centroid;
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        decre[lvl][u.fi]=decre[x];
        incre[lvl][u.fi]=incre[x];
        if(edgep<u.se) incre[lvl][u.fi]=false;
        if(edgep>u.se) decre[lvl][u.fi]=false;
        dfs(u.fi,x,u.se,centroid,lvl,edge , node);
    }
}
void build(int x,int lvl){
    int centroid=get_centroid(x,get_sz(x,-1),-1);
    parent[lvl][centroid]=centroid;
    belongs[lvl][centroid] = centroid;
    incre[lvl][centroid]=true;
    decre[lvl][centroid]=true;
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        cur=0;
        incre[lvl][u.fi] = true;
        decre[lvl][u.fi] = true;
        dfs(u.fi,centroid,u.se,centroid,lvl,u.se , u.fi);
        cnt[centroid].pb({u.se,cur});
    }
    removed[centroid]=true;
    for(auto u : adj[centroid]){
        if(removed[u.fi]) continue;
        build(u.fi,lvl+1);
    }
}
bool query(int x,int y,int t)
{
    if(x == y)
        return true;
    bool test=false;
    for(int lvl = 0 ; lvl < 20 ; lvl++)
    {
        if(belongs[lvl][x]==belongs[lvl][y] || parent[lvl][x] != parent[lvl][y]) continue;
        int centroid = parent[lvl][x];
        if(centroid == -1)
            continue;
        if(!decre[lvl][x] || !incre[lvl][y])
            continue;
        if(x == centroid)
        {
            test|=(join[lvl][y] <= t);
        }else if(y == centroid){
            test|=(up[lvl][x] <= t);
        }else
        {
            int edgep = up[lvl][x];
            test|= ((edgep <= t) && (join[lvl][y]<=edgep));
        }
    }
    return test;
}
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<20;i++){
        for(int j=0;j<n;j++){
            join[i][j]=1e9;
            up[i][j]=1e9;
            parent[i][j] = -1;
        }
    }
    vector<pair<char , pair<int,int>>> queries;
    for(int i = 0 ; i < n - 1 + k ; i++)
    {
        char c;
        cin>>c;
        if(c == 'S')
        {
            int a , b;
            cin>>a>>b;
            a-- , b--;
            adj[a].pb({b , i});
            adj[b].pb({a , i});
            queries.pb({c , {a , b}});
        }
        else if(c == 'Q')
        {
            int a , d;
            cin>>a>>d;
            a-- , d--;
            queries.pb({c , {a , d}});
        }else{
            int a;
            cin>>a;
            a--;
            queries.pb({c , {a , -1}});
        }
    }
    build(0,0);
    for(int i = 0 ; i < n - 1 + k ; i++)
    {
        auto Cur = queries[i];
        if(Cur.fi=='Q'){
            cout << (query(Cur.se.fi , Cur.se.se , i) ? "yes" : "no") <<endl;
        }
        // else if(Cur.fi=='C') cout << 0 <<endl;
        // if(cur.fi == 'C')
        // {
 
        // }
    }
}

Subtask #1
0 / 2.5

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

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 17600 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 155 ms 17824 KB Output is correct
2 Correct 243 ms 57724 KB Output is correct
3 Correct 316 ms 57652 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 155 ms 17824 KB Output is correct
2 Correct 243 ms 57724 KB Output is correct
3 Correct 316 ms 57652 KB Output is correct
4 Incorrect 144 ms 17604 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 156 ms 17600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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