Submission #567630

#	Time	Username	Problem	Language	Result	Execution time	Memory
567630		birthdaycake	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1480 ms	139088 KiB

bitaro

#include<bits/stdc++.h>
#define endl '\n'
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
 
const int sqt = 100;
 
 
vector<int>adj[200001],radj[200001];
 
int no[200001],dist[200001],sz[200001],dis[200001][150],c[200001][150],x[2000001];
signed main(){
    boost;
    
    int n,m,q; cin >> n >> m >> q;
    for(int i = 0; i < m; i++){
        int a,b;  cin >> a >> b;
        adj[a].push_back(b);
        radj[b].push_back(a);
    }
    
    
    for(int i = 1; i <= n; i++){
        vector<pair<int,int>>ds;
        ds.push_back({0,i});
        for(auto s:radj[i]){
            for(int j = 1; j <= sz[s]; j++){
                ds.push_back({dis[s][j] + 1, c[s][j]});
            }
        }
        sort(ds.begin(), ds.end(), greater<pair<int,int>>());
        for(int j = 0; j < ds.size(); j++){
            if(x[ds[j].second]) continue;
            dis[i][++sz[i]] = ds[j].first;
            c[i][sz[i]] = ds[j].second;
            x[ds[j].second] = 1;
            if(sz[i] > sqt) break;
        }
        x[i] = 0;
        for(auto s:radj[i]){
            x[s] = 0;
            for(int j = 1; j <= sz[s]; j++) x[c[s][j]] = 0;
        }
    }
    while(q--){
        int t,y, ans = -1; cin >> t >> y;
        set<int>f;
        if(y > sqt){
            for(int i = 1; i <= t; i++) no[i] = 0;
        }else{
            for(int i = 1; i <= sz[t]; i++) no[c[t][i]] = 0;
            no[t] = 0;
        }
        
        for(int i = 0; i < y; i++){
            int x; cin >> x;
            no[x] = 1;
        }
        if(y > sqt){
            for(int i = 1; i <= t; i++){
                if(no[i]) dist[i] = -INT_MAX;
                else dist[i] = 0;
                for(auto x:radj[i]) dist[i] = max(dist[i], dist[x] + 1);
            }
            ans = max(ans,dist[t]);
        }else{
            if(!no[t]) ans = 0;
            for(int j = 1; j <= sz[t]; j++){
                if(!no[c[t][j]]){
                    ans = dis[t][j];
                    break;
                }
            }
        }
        cout << ans << endl;
    }
    
    
    
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int j = 0; j < ds.size(); j++){
      |                        ~~^~~~~~~~~~~

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