Submission #414925

#	Time	Username	Problem	Language	Result	Execution time	Memory
414925		Pro_ktmr	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2077 ms	249384 KiB

bitaro

#pragma GCC target ("avx")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")

#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

const int B = 300; // sqrt(100000) = 316

int N, M, Q;
vector<int> e[100000];

vector<pair<int, int>> dp[100000];
bool used[100000] ={};

signed main(){
    cin >> N >> M >> Q;
    rep(i, M){
        int u, v;
        cin >> u >> v;
        e[v-1].pb(u-1);
    }

    rep(i, N){
        dp[i].pb({ 0,i });
        rep(j, e[i].size()){
            vector<pair<int, int>> tmp;
            vector<pair<int, int>> dpj;
            rep(k, dp[e[i][j]].size()){
                dpj.pb({ dp[e[i][j]][k].first+1, dp[e[i][j]][k].second });
            }
            int a = 0;
            int b = 0;
            rep(k, B){
                while(a < dp[i].size() && used[dp[i][a].second]){
                    a++;
                }
                while(b < dpj.size() && used[dpj[b].second]){
                    b++;
                }
                if(a == dp[i].size() && b == dpj.size()) break;
                if(a == dp[i].size()){
                    tmp.pb(dpj[b]);
                    used[dpj[b].second] = true;
                    b++;
                    continue;
                }
                if(b == dpj.size()){
                    tmp.pb(dp[i][a]);
                    used[dp[i][a].second] = true;
                    a++;
                    continue;
                }
                if(dpj[b] >= dp[i][a]){
                    tmp.pb(dpj[b]);
                    used[dpj[b].second] = true;
                    b++;
                }
                else{
                    tmp.pb(dp[i][a]);
                    used[dp[i][a].second] = true;
                    a++;
                }
            }
            rep(k, tmp.size()){
                used[tmp[k].second] = false;
            }
            dp[i] = tmp;
        }
    }

    rep(q, Q){
        int T, Y;
        cin >> T >> Y;
        T--;
        unordered_set<int> st;
        rep(i, Y){
            int C;
            cin >> C;
            st.insert(C-1);
        }
        if(Y >= B){
            vector<int> dp(N);
            rep(i, T+1){
                if(st.count(i) == 0) dp[i] = 0;
                else dp[i] = INT_MIN;
                rep(j, e[i].size()){
                    dp[i] = max(dp[i], dp[e[i][j]]+1);
                }
            }
            cout << max(-1, dp[T]) << endl;
        }
        else{
            rep(i, dp[T].size()){
                if(st.count(dp[T][i].second) == 0){
                    cout << dp[T][i].first << endl;
                    break;
                }
                if(i == dp[T].size()-1) cout << -1 << endl;
            }
        }
    }
}

/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5
*/

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:29:5: note: in expansion of macro 'rep'
   29 |     rep(i, M){
      |     ^~~
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:35:5: note: in expansion of macro 'rep'
   35 |     rep(i, N){
      |     ^~~
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:37:9: note: in expansion of macro 'rep'
   37 |         rep(j, e[i].size()){
      |         ^~~
bitaro.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
bitaro.cpp:37:9: note: in expansion of macro 'rep'
   37 |         rep(j, e[i].size()){
      |         ^~~
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:40:13: note: in expansion of macro 'rep'
   40 |             rep(k, dp[e[i][j]].size()){
      |             ^~~
bitaro.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
bitaro.cpp:40:13: note: in expansion of macro 'rep'
   40 |             rep(k, dp[e[i][j]].size()){
      |             ^~~
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:45:13: note: in expansion of macro 'rep'
   45 |             rep(k, B){
      |             ^~~
bitaro.cpp:46:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |                 while(a < dp[i].size() && used[dp[i][a].second]){
      |                       ~~^~~~~~~~~~~~~~
bitaro.cpp:49:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                 while(b < dpj.size() && used[dpj[b].second]){
      |                       ~~^~~~~~~~~~~~
bitaro.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                 if(a == dp[i].size() && b == dpj.size()) break;
      |                    ~~^~~~~~~~~~~~~~~
bitaro.cpp:52:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                 if(a == dp[i].size() && b == dpj.size()) break;
      |                                         ~~^~~~~~~~~~~~~
bitaro.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                 if(a == dp[i].size()){
      |                    ~~^~~~~~~~~~~~~~~
bitaro.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                 if(b == dpj.size()){
      |                    ~~^~~~~~~~~~~~~
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:76:13: note: in expansion of macro 'rep'
   76 |             rep(k, tmp.size()){
      |             ^~~
bitaro.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
bitaro.cpp:76:13: note: in expansion of macro 'rep'
   76 |             rep(k, tmp.size()){
      |             ^~~
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'q' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:83:5: note: in expansion of macro 'rep'
   83 |     rep(q, Q){
      |     ^~~
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:88:9: note: in expansion of macro 'rep'
   88 |         rep(i, Y){
      |         ^~~
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:95:13: note: in expansion of macro 'rep'
   95 |             rep(i, T+1){
      |             ^~~
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:98:17: note: in expansion of macro 'rep'
   98 |                 rep(j, e[i].size()){
      |                 ^~~
bitaro.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
bitaro.cpp:98:17: note: in expansion of macro 'rep'
   98 |                 rep(j, e[i].size()){
      |                 ^~~
bitaro.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
bitaro.cpp:105:13: note: in expansion of macro 'rep'
  105 |             rep(i, dp[T].size()){
      |             ^~~
bitaro.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
bitaro.cpp:105:13: note: in expansion of macro 'rep'
  105 |             rep(i, dp[T].size()){
      |             ^~~
bitaro.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |                 if(i == dp[T].size()-1) cout << -1 << endl;
      |                    ~~^~~~~~~~~~~~~~~~~

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