Submission #47810

#	Time	Username	Problem	Language	Result	Execution time	Memory
47810		mirbek01	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1598 ms	211476 KiB

bitaro

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;
const int B = 200;

int n, m, q, used[N], dp[N];
vector <int> g[N];
vector < pair <int, int> > vd[N];

vector < pair <int, int> > get(vector < pair <int, int> > a, vector < pair <int, int> > b){
      vector < pair <int, int> > res;

      for(int i = 0; i < b.size(); i ++)
            b[i].first ++;

      int i = 0, j = 0;

      while(i < a.size() && j < b.size() && res.size() <= B){
            pair <int, int> p;
            if(a[i].first > b[j].first){
                  p = a[i ++];
            } else {
                  p = b[j ++];
            }
            if(!used[p.second]){
                  res.push_back(p);
                  used[p.second] = 1;
            }
      }

      while(i < a.size() && res.size() <= B){
            pair <int, int> p = a[i ++];
            if(!used[p.second]){
                  res.push_back(p);
                  used[p.second] = 1;
            }
      }

      while(j < b.size() && res.size() <= B){
            pair <int, int> p = b[j ++];
            if(!used[p.second]){
                  res.push_back(p);
                  used[p.second] = 1;
            }
      }

      for(int i = 0; i < res.size(); i ++)
            used[res[i].second] = 0;

      return res;
}

int main(){
      scanf("%d %d %d", &n, &m, &q);

      for(int i = 1; i <= m; i ++){
            int u, v;
            scanf("%d %d", &u, &v);
            g[v].emplace_back(u);
      }

      for(int i = 1; i <= n; i ++){
            vd[i].push_back({0, i});
            for(int to : g[i]){
                  vd[i] = get(vd[i], vd[to]);
            }
      }

      while(q --){
            int t, y;
            vector <int> v;
            scanf("%d %d", &t, &y);

            for(int i = 1; i <= y; i ++){
                  int x;
                  scanf("%d", &x);
                  used[x] = 1;
                  v.emplace_back(x);
            }

            if(y >= B){
                  for(int i = 1; i <= t; i ++){
                        dp[i] = 0;
                        for(int to : g[i]){
                              used[i] = min(used[to], used[i]);
                              if(!used[to]){
                                    dp[i] = max(dp[i], dp[to] + 1);
                              }
                        }
                  }

                  if(used[t]) dp[t] --;

                  printf("%d\n", dp[t]);
            } else {
                  int ans = -1;

                  for(int i = 0; i < vd[t].size(); i ++){
                        int f = vd[t][i].first, s = vd[t][i].second;
                        if(used[s]) continue;
                        ans = max(ans, f);
                  }

                  printf("%d\n", ans);
            }

            for(int i : v)
                  used[i] = 0;
      }
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > get(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:15:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < b.size(); i ++)
                      ~~^~~~~~~~~~
bitaro.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(i < a.size() && j < b.size() && res.size() <= B){
             ~~^~~~~~~~~~
bitaro.cpp:20:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(i < a.size() && j < b.size() && res.size() <= B){
                             ~~^~~~~~~~~~
bitaro.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(i < a.size() && res.size() <= B){
             ~~^~~~~~~~~~
bitaro.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(j < b.size() && res.size() <= B){
             ~~^~~~~~~~~~
bitaro.cpp:49:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < res.size(); i ++)
                      ~~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:100:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int i = 0; i < vd[t].size(); i ++){
                                  ~~^~~~~~~~~~~~~~
bitaro.cpp:56:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d", &n, &m, &q);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &t, &y);
             ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:78:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                   scanf("%d", &x);
                   ~~~~~^~~~~~~~~~

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