oj.uz

Submission #65858

# Submission time Handle Problem Language Result Execution time Memory
65858 2018-08-09T04:33:48 Z funcsr Bitaro’s Party (JOI18_bitaro) C++17
7 / 100
 2000 ms 262076 KB 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
const int B = 320;

int N, M, Q;
vector<int> G[100000], Grev[100000];
int D[100000];
bool BAD[100000];
vector<P> dp[100000];
bool used[100000];

vector<P> filter(vector<P> seq) {
  vector<P> ret;
  for (P p : seq) if (!used[p._2]) ret.pb(p), used[p._2] = true;
  for (P p : seq) used[p._2] = false;
  if (ret.size() > B) ret.resize(B);
  return ret;
}

vector<P> merge(vector<P> a, vector<P> b) {
  vector<P> ret;
  int x = 0, y = 0;
  while (x<a.size() && y<b.size()) {
    if (a[x]>=b[y]) ret.pb(a[x++]);
    else ret.pb(b[y++]);
  }
  while (x<a.size()) ret.pb(a[x++]);
  while (y<b.size()) ret.pb(b[y++]);
  return filter(ret);
}

int solve(int s, vector<int> bad) {
  rep(i, N) D[i] = -1;
  D[s] = 0;
  int m = -1;
  for (int x=s; x>=0; x--) if (D[x] != -1) {
    if (!BAD[x]) m = max(m, D[x]);
    for (int t : Grev[x]) D[t] = max(D[t], D[x]+1);
  }
  return m;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M >> Q;
  rep(i, M) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].pb(b);
    Grev[b].pb(a);
  }
  rep(x, N) dp[x].pb(P(0, x));
  rep(x, N) {
    vector<P> seq(dp[x]);
    for (P &p : seq) p._1++;
    for (int t : G[x]) dp[t] = merge(dp[t], seq);
  }

  rep(i, Q) {
    int x, k;
    cin >> x >> k;
    x--;
    vector<int> bad(k);
    rep(i, k) cin >> bad[i], bad[i]--;
    for (int i : bad) BAD[i] = true;

    if (k < B) {
      int m = -1;
      for (P p : dp[x]) if (!BAD[p._2]) m = max(m, p._1);
      cout << m << "\n";
    }
    else {
      cout << solve(x, bad) << "\n";
    }
    for (int i : bad) BAD[i] = false;
  }
  return 0;
}

Compilation message

bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:46:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (x<a.size() && y<b.size()) {
          ~^~~~~~~~~
bitaro.cpp:46:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (x<a.size() && y<b.size()) {
                        ~^~~~~~~~~
bitaro.cpp:50:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (x<a.size()) ret.pb(a[x++]);
          ~^~~~~~~~~
bitaro.cpp:51:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (y<b.size()) ret.pb(b[y++]);
          ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 39 ms 7596 KB Output is correct
4 Correct 8 ms 7620 KB Output is correct
5 Correct 16 ms 8036 KB Output is correct
6 Correct 9 ms 8060 KB Output is correct
7 Correct 11 ms 8180 KB Output is correct
8 Correct 22 ms 11456 KB Output is correct
9 Correct 25 ms 11556 KB Output is correct
10 Correct 24 ms 11556 KB Output is correct
11 Correct 28 ms 11556 KB Output is correct
12 Correct 17 ms 11556 KB Output is correct
13 Correct 25 ms 11556 KB Output is correct
14 Correct 22 ms 11556 KB Output is correct
15 Correct 17 ms 11556 KB Output is correct
16 Correct 22 ms 11556 KB Output is correct
17 Correct 23 ms 11556 KB Output is correct
18 Correct 19 ms 11556 KB Output is correct
19 Correct 24 ms 11556 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 39 ms 7596 KB Output is correct
4 Correct 8 ms 7620 KB Output is correct
5 Correct 16 ms 8036 KB Output is correct
6 Correct 9 ms 8060 KB Output is correct
7 Correct 11 ms 8180 KB Output is correct
8 Correct 22 ms 11456 KB Output is correct
9 Correct 25 ms 11556 KB Output is correct
10 Correct 24 ms 11556 KB Output is correct
11 Correct 28 ms 11556 KB Output is correct
12 Correct 17 ms 11556 KB Output is correct
13 Correct 25 ms 11556 KB Output is correct
14 Correct 22 ms 11556 KB Output is correct
15 Correct 17 ms 11556 KB Output is correct
16 Correct 22 ms 11556 KB Output is correct
17 Correct 23 ms 11556 KB Output is correct
18 Correct 19 ms 11556 KB Output is correct
19 Correct 24 ms 11556 KB Output is correct
20 Correct 1299 ms 13804 KB Output is correct
21 Correct 1248 ms 14068 KB Output is correct
22 Correct 1375 ms 14068 KB Output is correct
23 Correct 1663 ms 14068 KB Output is correct
24 Execution timed out 2063 ms 262076 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 39 ms 7596 KB Output is correct
4 Correct 8 ms 7620 KB Output is correct
5 Correct 16 ms 8036 KB Output is correct
6 Correct 9 ms 8060 KB Output is correct
7 Correct 11 ms 8180 KB Output is correct
8 Correct 22 ms 11456 KB Output is correct
9 Correct 25 ms 11556 KB Output is correct
10 Correct 24 ms 11556 KB Output is correct
11 Correct 28 ms 11556 KB Output is correct
12 Correct 17 ms 11556 KB Output is correct
13 Correct 25 ms 11556 KB Output is correct
14 Correct 22 ms 11556 KB Output is correct
15 Correct 17 ms 11556 KB Output is correct
16 Correct 22 ms 11556 KB Output is correct
17 Correct 23 ms 11556 KB Output is correct
18 Correct 19 ms 11556 KB Output is correct
19 Correct 24 ms 11556 KB Output is correct
20 Correct 1299 ms 13804 KB Output is correct
21 Correct 1248 ms 14068 KB Output is correct
22 Correct 1375 ms 14068 KB Output is correct
23 Correct 1663 ms 14068 KB Output is correct
24 Execution timed out 2063 ms 262076 KB Time limit exceeded
25 Halted 0 ms 0 KB -