제출 #567592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
567592		birthdaycake	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	7 ms	9684 KiB

bitaro

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
 
const int sqt = 70;
 
 
vector<int>adj[200001],radj[200001];
 
int no[200001],dist[200001],sz[200001],dis[200001][71],c[200001][71];
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>>());
        set<int>x;
        for(int j = 0; j < ds.size(); j++){
            if(x.count(ds[j].second)) continue;
            dis[i][++sz[i]] = ds[j].first;
            c[i][sz[i]] = ds[j].second;
            x.insert(ds[j].second);
        }
    }
    while(q--){
        int t,y, ans = -1; cin >> t >> y;
        set<int>f;
        for(int i = 0; i < y; i++){
            int x; cin >> x;
            f.insert(x);
        }
        if(y > sqt){
            for(int i = 1; i <= t; i++){
                if(f.count(i)) dist[i] = -1e18;
                else dist[i] = 0;
                for(auto x:radj[i]){
                    dist[i] = max(dist[i], dist[x] + 1);
                }
                if(!f.count(i)) ans = max(ans,dist[t]);

            }
        }else{
            for(int j = 1; j <= sqt + 1; j++){
                if(!f.count(c[t][j])){
                    ans = dis[t][j];
                    break;
                }
            }
        }
        cout << ans << endl;
    }
    
    
    
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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