Submission #1016597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016597		Ludissey	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	2 ms	604 KiB

bitaro

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define last(a) a[sz(a)-1]

using namespace std;

vector<int> memo;
vector<vector<int>> neigh;
vector<vector<int>> neigh2;
vector<int> topo;
vector<int> tin;
vector<int> out;
int timer=0;

int dp(int x){
    if(memo[x]>-1) return memo[x];
    memo[x]=0;
    for (auto u : neigh[x]) memo[x]=max(memo[x],dp(u)+1);
    topo.push_back(memo[x]);
    tin[x]=timer;
    timer++;
    return memo[x];
}

void dp2(int x, int t){
    out[x]=t;
    for (auto u : neigh2[x]) dp2(u,out[x]);
    return;
}

struct node{
    node* left; node* right;
    int mx;
    void update(){
        this->mx=min(left->mx,right->mx);
    }
};
struct Segtree {
    int n;
    node* root;
    int base=1e9;
    Segtree(int _n) {
        this->n = _n;
        root=new node{NULL,NULL,0};
    }
    void build(node* x, int l, int r, vector<int> const &a){
        if(l==r) {
            x->mx=a[l];
            return;
        }
        int mid=(l+r)/2;
        x->left=new node{NULL,NULL,0};
        x->right=new node{NULL,NULL,0};
        build(x->left,l,mid,a);
        build(x->right,mid+1,r,a);
        x->update();
    }

    Segtree(vector<int> const &a) : Segtree(a.size()) {
        build(root,0,n-1,a);
    }
    int query(node* x, int l, int r, int qL, int qR){
        if(r<qL||l>qR) return base;
        if(l>=qL&&r<=qR) return x->mx;
        int mid=(l+r)/2;
        return min(query(x->left,l,mid,qL,qR),query(x->right,mid+1,r,qL,qR));
    }
    int query(int l, int r){
        return query(root,0,n-1,l,r);
    }
    void update(node* x, int l, int r, int p, int v){
        if(r<p||l>p) return;
        if(l==r&&l==p) { x->mx=v; return; }
        int mid=(l+r)/2;
        update(x->left,l,mid,p,v);
        update(x->right,mid+1,r,p,v);
        x->update();
    }
    void update(int p, int v){
        update(root,0,n-1,p,v);
    }
};

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N,M,Q; cin >> N >> M >> Q;
    memo.resize(N,-1);        
    neigh.resize(N);
    neigh2.resize(N);
    tin.resize(N);
    out.resize(N);
    timer=0;
    vector<bool> leaf(N,true);
    vector<bool> root(N,true);
    for (int i = 0; i < M; i++)
    {
        int a,b; cin >> a >> b;
        a--; b--;
        neigh[b].push_back(a);
        neigh2[a].push_back(b);
        leaf[a]=false;
        root[b]=false;
    }
    for (int i = 0; i < N; i++)
    {
       if(leaf[i]) dp(i);
    }
    for (int i = 0; i < N; i++)
    {
       if(root[i]) dp2(i,tin[i]);
    }
    Segtree seg(topo);
    while (Q--)
    {
        int T,Y; cin >> T >> Y;
        vector<int> y(Y);
        for (int i = 0; i < Y; i++)
        {
            cin >> y[i];
            y[i]--;
            seg.update(tin[y[i]],1e9);
        }

        int q=seg.query(out[T-1],tin[T-1]);
        cout << max(-1LL,topo[tin[T-1]]-q) << "\n";

        for (int i = 0; i < Y; i++)
        {
            seg.update(tin[y[i]],topo[tin[y[i]]]);
        }
    }
    
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86