Submission #201496

#	Time	Username	Problem	Language	Result	Execution time	Memory
201496		Sensei	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	2086 ms	330616 KiB

bitaro

/*
  DATE:    2020-02-10 20:58:45
  NAME:    
  PROBLEM: JOI18_BITARO
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

int a[MAXN + 7];

vector<int> edge[MAXN + 7];
vector<int> redge[MAXN + 7];

class AnsSet {
  multiset<pair<int, int> > ms;
  int level;
public:
  AnsSet() {
    level = 0;
  }
  int size() {
    return ms.size();
  }
  void increase_level() {
    level++;
  }
  int get_max_allowed(set<int> &disallowed) {
    multiset<pair<int, int> >::reverse_iterator it = ms.rbegin();
    while (it != ms.rend() and disallowed.find(it->second) != disallowed.end()) {
      it++;
    }
    if (it == ms.rend()) {
      return -1;
    }
    else {
      return it->first + level;
    }
  }
  pair<int, int> top() {
    return {ms.begin()->first + level, ms.begin()->second};
  }
  void pop() {
    ms.erase(ms.begin());
  }
  void push(pair<int, int> x) {
    ms.insert({x.first - level, x.second});
  }
  void merge(AnsSet set2) {
    // assert(set2.size() <= (int) ms.size());

    while (set2.size() > 0) {
      push(set2.top());
      set2.pop();
    }
  }
};

AnsSet ans_sets[MAXN + 7];

deque<int> ts;
bool vis[MAXN + 7];

void dfs(int root) {
  vis[root] = true;
  for (int i = 0; i < edge[root].size(); i++) {
    int child = edge[root][i];
    if (!vis[child]) {
      dfs(child);
    }
  }
  ts.push_front(root);
}

int ans[MAXN + 7];
vector<pair<int, set<int> > > disallowed_nodes[MAXN + 7];

int main() {
  int n, m, q;
  cin >> n >> m >> q;

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

  for (int i = 1; i <= q; i++) {
    int u;
    scanf("%d", &u);
    int cnt;
    scanf("%d", &cnt);
    pair<int, set<int> > qry;
    qry.first = i;
    for (int j = 1; j <= cnt; j++) {
      int v;
      scanf("%d", &v);
      qry.second.insert(v);
    }
    disallowed_nodes[u].push_back(qry);
  }

  for (int u = 1; u <= n; u++) {
    if (!vis[u]) {
      dfs(u);
    }
  }

  ts.push_front(0);

  for (int i = 1; i < ts.size(); i++) {
    int u = ts[i];
    // cerr << i << " " << u << "\n";

    ans_sets[u].increase_level();

    ans_sets[u].push({0, u});

    for (int j = 0; j < disallowed_nodes[u].size(); j++) {
      // cerr << disallowed_nodes[u][j].first << "\t";
      // cerr << ans_sets[u].size() << "\t";
      // cerr << ans_sets[u].get_max_allowed(disallowed_nodes[u][j].second) << "\n";
      ans[disallowed_nodes[u][j].first] = ans_sets[u].get_max_allowed(disallowed_nodes[u][j].second);
    }

    for (int j = 0; j < edge[u].size(); j++) {
      int v = edge[u][j];
      ans_sets[v].merge(ans_sets[u]);
    }

    while (ans_sets[u].size() > 0) {
      ans_sets[u].pop();
    }
  }

  for (int i = 1; i <= q; i++) {
    printf("%d\n", ans[i]);
  }

  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void dfs(int)':
bitaro.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edge[root].size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:114:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < ts.size(); i++) {
                   ~~^~~~~~~~~~~
bitaro.cpp:122:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < disallowed_nodes[u].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:129:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < edge[u].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~
bitaro.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &u, &v);
     ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &u);
     ~~~~~^~~~~~~~~~
bitaro.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &cnt);
     ~~~~~^~~~~~~~~~~~
bitaro.cpp:100:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &v);
       ~~~~~^~~~~~~~~~

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