제출 #1010255

#제출 시각아이디문제언어결과실행 시간메모리
1010255phongBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2028 ms146008 KiB
#include<bits/stdc++.h>

#define ll long long
const int nmax = 2e5 + 5, N = 3e5 + 5;
const ll oo = 1e18;
const int lg = 18, M = 4e3;
const int base = 2e5, mod = 1e9 + 7;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';cout << endl
using namespace std;


vector<int> adj[nmax];
vector<pii> gg[nmax];
int n, m, q;
int vis[nmax], c[nmax], dp[nmax];
int res[nmax], a[nmax];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//        freopen("code.inp", "r", stdin);
//        freopen("code.out", "w", stdout);
    cin >> n >> m >> q;
    for(int i = 1, u, v; i <= m; ++i){
        cin >> u >> v;
        adj[v].push_back(u);
    }
    int S = 100;
    vector<pii> tmp;
    for(int i = 1; i <= n; ++i){
        gg[i].push_back({0, i});
        for(auto v : adj[i]){
            for(auto [d, x] : gg[v]){
                tmp.push_back({d + 1, x});
                res[x] = max(res[x], d + 1);
            }
        }
        for(auto [d, x] : tmp){
            if(res[x] == d){
                gg[i].push_back({d, x});
                res[x] = 0;
            }
        }
        sort(gg[i].begin(), gg[i].end(), [](pii a, pii b){
             return a.fi > b.fi;
             });
        while(gg[i].size() > S) gg[i].pop_back();
//        for(auto [d, x] : gg[i]) cout << x << ' ';
//        cout << endl;
    }


    while(q--){
        int t, y;
        cin >> t >> y;
        if(y >= S){
            for(int i = 1, x; i <= y; ++i) cin >> x, c[x] = 1;
            for(int i = 1; i <= n; ++i) dp[i] = -n;
            dp[t] = 0;
            for(int i = t; i >= 1; --i){
                for(auto v : adj[i]){
//                    cout << i << ' ' << v << endl;
                    dp[v] = max(dp[v], dp[i] + 1);
                }
            }
            int ans = -1;
            for(int i = 1; i <= t; ++i){
                if(c[i]) continue;
//                cout << i << ' ' << dp[i] << endl;
                ans = max(ans, dp[i]);
            }
            for(int i = 1; i <= n; ++i)c[i] =dp[i]= 0;
            cout << ans << endl;
        }
        else{
            for(int i = 1,x; i <= y; ++i){
                cin >> x, c[x] = 1;
                a[i] = x;
            }
            bool ok = 0;
            for(auto [d, x] : gg[t]){
                if(c[x]) continue;
                cout << d << endl;
                ok = 1;
                break;
            }
            for(int i = 1; i <= y; ++i) c[a[i]] = 0;
            if(!ok) cout << -1 << endl;

        }
    }
}
/*


*/

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

bitaro.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(){
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:50:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         while(gg[i].size() > S) gg[i].pop_back();
      |               ~~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...