Submission #394593

#	Time	Username	Problem	Language	Result	Execution time	Memory
394593		Osama_Alkhodairy	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1358 ms	414504 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;
const int INF = (int)1e9;

int n, m, q, vis1[N], vis2[N];
vector <int> 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--;
        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> dist(t + 1, -INF);
            dist[t] = 0;
            int ans = -1;
            for(int j = t ; j >= 0 ; j--){
                for(auto &k : g[j]){
                    dist[k] = max(dist[k], 1 + dist[j]);
                }
                if(vis1[j] != i) ans = max(ans, dist[j]);
            }
            cout << ans << "\n";
        }
    }
}

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