Submission #394589

#	Time	Username	Problem	Language	Result	Execution time	Memory
394589		Osama_Alkhodairy	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	7 ms	7756 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 100001;
const int K = 300;

int n, m, q, vis1[N], vis2[N];
vector <int> v[N], g[N];
vector <pair <int, int> > f[N];
int curt;

vector <pair <int, int> > merge(vector <pair <int, int> > &l, vector <pair <int, int> > &r){
    curt++;
    vector <pair <int, int> > ret;
    int lpos = 0, rpos = 0;
    int lsz = l.size(), rsz = r.size();
    while(ret.size() < K && (lpos < lsz || rpos < rsz)){
        pair <int, int> winner;
        if(lpos == lsz){
            winner = make_pair(r[rpos].first + 1, r[rpos].second);
            rpos++;
        }
        else if(rpos == rsz){
            winner = l[lpos];
            lpos++;
        }
        else if(l[lpos].first > r[rpos].first + 1){
            winner = l[lpos];
            lpos++;
        }
        else{
            winner = make_pair(r[rpos].first + 1, r[rpos].second);
            rpos++;
        }
        if(vis2[winner.second] == curt) continue;
        vis2[winner.second] = curt;
        ret.push_back(winner);
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 0 ; i < m ; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        v[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 0 ; i < n ; i++){
        f[i].push_back(make_pair(0, i));
        for(auto &j : g[i]){
            f[i] = merge(f[i], f[j]);
        }
    }
    for(int i = 1 ; i <= q ; i++){
        int t, sz;
        cin >> t >> sz;
        t--;
        for(int j = 0 ; j < sz ; j++){
            int x;
            cin >> x;
            x--;
            vis1[x] = i;
        }
        //~ if(sz < K){
            //~ int ans = -1;
            //~ for(auto &j : f[t]){
                //~ if(vis1[j.second] == i) continue;
                //~ ans = j.first;
                //~ break;
            //~ }
            //~ cout << ans << "\n";
        //~ }
        //~ else{
            vector <int> ans(n, 0);
            for(int j = 0 ; j <= t ; j++){
                if(vis1[j] == i) continue;
                for(auto &k : v[j]){
                    ans[k] = max(ans[k], 1 + ans[j]);
                }
            }
            if(ans[t] == 0 && vis1[t] == i) cout << "-1\n";
            else cout << ans[t] << "\n";
        //~ }
    }
}

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