QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133954#4938. Writing TasksRd_rainydaysWA 104ms76732kbC++203.6kb2023-08-02 18:15:552023-08-02 18:15:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 18:15:59]
  • 评测
  • 测评结果:WA
  • 用时:104ms
  • 内存:76732kb
  • [2023-08-02 18:15:55]
  • 提交

answer

#include <bits/stdc++.h>
using std::vector;
using std::tuple;
#define all(x) (x).begin(), (x).end()

const int N = 400005;
int A, C, T;
vector<int> L[N], F[N], S[N], ps[N];

int tot;
vector<tuple<int, int>> es;
vector<int> adj[N];

std::map<tuple<int, int>, int> id;
vector<int> vs[N];

bool vis[N];
void solve() {
  for (int i = 1; i <= tot; i++)
    assert(adj[i].size() <= 2u);

  vector<int> ids;
  bool isRing = 0;
  int head = -1;
  auto dfs = [&](int x, int f, auto& dfs) -> void {
    ids.push_back(x);
    // printf("  dfs log : %d\n", x);
    vis[x] = 1;
    if (adj[x].size() == 1u) head = x;
    for (auto y : adj[x]) if (y != f) {
      if (vis[y] == 1) { isRing = 1; break; }
      dfs(y, x, dfs);
    }
  };

  int ans = 0;
  for (int i = 1; i <= tot; i++) {
    if (vis[i]) continue;

    isRing = 0, head = -1;
    ids.clear();
    dfs(i, 0, dfs);
    if (head != -1 && isRing) std::reverse(ids.begin(), std::find(all(ids), head) + 1);

    // printf(" %s :", (isRing ? "Ring" : "Chain"));
    // for (int id : ids)  
    //   printf(" %d ", id);
    // puts("");

    vector<std::array<int, 3>> dp(ids.size());    
    auto do_trans = [&](int exclude) -> int {
      for (int j = 1; j < (int)ids.size(); j++) {
        int cur = ids[j], pre = ids[j - 1];
        for (int t = 0; t < (int)vs[cur].size(); t++)
          dp[j][t + 1] = dp[j - 1][0] + 1;
        dp[j][0] = *std::max_element(all(dp[j - 1]));
        // trivial

        for (int t = 0; t < (int)vs[cur].size(); t++)
          for (int s = 0; s < (int)vs[pre].size(); s++) {
            if (vs[cur][t] == vs[pre][s]) continue;
            dp[j][t + 1] = std::max(dp[j][t + 1], dp[j - 1][s + 1] + 1);
          }
      }
      
      int cur_ans = 0;
      for (int i = 0; i < 3; i++) {
        if (i == exclude && exclude > 0) continue;
        cur_ans = std::max(cur_ans, dp.back()[i]);
      }
      return cur_ans;
    };

    if (!isRing) {
      dp.assign(ids.size(), {0, 0, 0});
      dp[0][0] = 0;
      for (int t = 0; t < (int)vs[ids[0]].size(); t++)
        dp[0][t + 1] = 1;
      ans += do_trans(0);
    } else {
      vector<int> cadi;
      for (int ex = 0; ex <= (int)vs[ids[0]].size(); ex++) {
        dp.assign(ids.size(), {0, 0, 0});
        dp[0][ex] = (ex > 0);
        cadi.push_back(do_trans(ex));
      }
      ans += *std::max_element(all(cadi));
    }

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

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

int main() {
  scanf("%d%d%d", &A, &C, &T);

  for (int i = 1; i <= A; i++) {
    int sz;
    scanf("%d", &sz);
    L[i].resize(sz);
    for (auto &x : L[i]) scanf("%d", &x);
  }

  for (int i = 1; i <= A; i++) {
    int sz;
    scanf("%d", &sz);
    F[i].resize(sz);
    for (auto &x : F[i]) scanf("%d", &x);
  }

  for (int i = 1; i <= C; i++) {
    int sz;
    scanf("%d", &sz);
    S[i].resize(sz);
    for (auto &x : S[i]) {
      scanf("%d", &x);
      ++tot;
      ps[x].push_back(tot);
      id[{i, x}] = tot;
    }
    if (sz == 2)
      es.emplace_back(tot - 1, tot);
  }

  for (int i = 1; i <= T; i++)
    if ((int)ps[i].size() == 2)
      es.emplace_back(ps[i][0], ps[i][1]);
  for (int i = 1; i <= A; i++)
    for (auto l : L[i]) for (auto f : F[i])
      vs[id[{l, f}]].push_back(i);
  
  for (auto &[a, b] : es)
    if (a > b) std::swap(a, b);
  
  std::sort(all(es));
  es.erase(std::unique(all(es)), es.end());
  for (auto [a, b] : es) {
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  solve();
  return 0;
}
/*
2 3 2
2 1 2
2 2 3
1 1
1 1
1 1
1 1
1 2

3 4 3
1 2
2 4 2
2 1 3
1 1
2 2 3
2 3 2
1 3
2 1 3
1 2
1 2
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 59976kb

input:

2 3 2
2 1 2
2 2 3
1 1
1 1
1 1
1 1
1 2

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 1ms
memory: 60052kb

input:

2 2 2
0
1 2
0
2 1 2
2 1 2
0

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 88ms
memory: 74908kb

input:

40623 39265 42226
2 14643 37432
2 29610 20181
2 6441 7614
2 17559 3238
2 39001 17644
2 6431 37097
2 6347 12246
2 1130 1688
2 38583 9078
2 8746 27832
2 13090 39048
2 32647 18777
2 27505 19277
2 31201 25824
2 6133 20344
2 11625 20997
2 18528 35730
0
2 22986 5273
2 10942 38791
2 19025 35679
2 32321 124...

output:

78528

result:

ok single line: '78528'

Test #4:

score: 0
Accepted
time: 81ms
memory: 75060kb

input:

41022 39421 42288
2 26413 2168
2 24182 14199
2 18798 17846
2 3398 19624
2 16796 33998
2 7209 25883
2 26356 13537
2 56 30294
2 34909 20218
2 29727 22116
2 16349 1704
2 9254 18036
2 16197 16096
2 21562 31470
2 14773 10518
2 38025 12573
2 15509 32276
2 9613 12321
2 19146 11395
2 7186 36431
0
2 10098 22...

output:

78840

result:

ok single line: '78840'

Test #5:

score: 0
Accepted
time: 104ms
memory: 76732kb

input:

49395 43808 45888
2 13031 11323
2 41375 4393
2 32137 17908
2 29053 42691
0
2 38335 30970
2 38318 43773
2 22999 22444
0
2 39248 30837
0
2 29807 2360
2 29363 3536
2 8515 41137
2 7890 31441
0
2 31070 6987
2 24295 15517
2 14204 13069
2 32996 40146
2 38164 1478
2 40032 19143
0
2 18430 24119
2 37845 33290...

output:

87616

result:

ok single line: '87616'

Test #6:

score: 0
Accepted
time: 4ms
memory: 59976kb

input:

3 4 3
1 2
2 4 2
2 1 3
1 1
2 2 3
2 3 2
1 3
2 1 3
1 2
1 2

output:

5

result:

ok single line: '5'

Test #7:

score: 0
Accepted
time: 8ms
memory: 60316kb

input:

15 17 18
1 12
2 13 4
2 2 6
2 11 14
2 7 3
2 17 11
2 4 8
2 5 1
1 1
1 16
1 3
2 10 16
1 8
2 15 5
1 6
2 6 1
2 7 3
1 13
2 12 9
2 8 18
1 9
2 1 15
2 5 13
2 18 14
2 15 7
1 4
2 10 2
1 2
1 17
2 14 17
1 18
1 13
1 4
1 1
1 5
2 14 3
2 8 16
2 2 16
1 10
1 10
2 12 14
1 6
2 7 15
2 6 3
2 17 12
1 15
1 9

output:

15

result:

ok single line: '15'

Test #8:

score: 0
Accepted
time: 9ms
memory: 60652kb

input:

769 869 792
1 254
2 210 794
1 863
2 40 403
2 279 773
2 54 328
2 196 473
1 804
1 261
1 174
1 219
1 22
1 429
1 195
2 769 100
1 33
1 457
1 604
2 473 714
2 423 227
2 453 654
1 864
2 220 243
2 520 321
2 421 805
2 721 11
2 216 793
1 360
1 169
2 121 613
2 714 594
1 692
2 642 607
2 538 781
2 800 387
2 494 5...

output:

769

result:

ok single line: '769'

Test #9:

score: 0
Accepted
time: 83ms
memory: 75252kb

input:

46352 41211 38602
2 11300 5679
2 2876 4114
2 28525 6628
1 23785
1 30940
1 26982
1 8056
1 13748
2 25254 21974
1 3446
2 2294 13453
0
1 16724
2 36970 18406
2 7688 17413
1 25901
1 39238
1 16098
1 29911
2 15113 849
1 31293
2 32195 13287
0
1 12670
2 40732 19567
2 24195 23787
1 40913
2 18820 10009
0
0
2 23...

output:

38602

result:

ok single line: '38602'

Test #10:

score: 0
Accepted
time: 8ms
memory: 59984kb

input:

3 4 3
1 4
2 1 3
2 3 4
2 1 2
2 3 1
1 2
1 3
0
1 2
2 1 2

output:

3

result:

ok single line: '3'

Test #11:

score: -100
Wrong Answer
time: 13ms
memory: 60060kb

input:

15 15 20
2 12 14
2 1 3
1 11
2 5 13
2 8 9
1 13
1 9
2 15 11
2 3 6
2 6 7
1 10
1 2
2 7 12
1 14
1 4
1 3
1 1
2 12 20
2 18 2
2 10 15
2 2 10
2 15 18
2 17 3
2 6 7
2 16 17
1 19
2 13 6
1 14
2 4 11
2 8 16
2 1 4
1 13
2 6 1
1 8
1 18
2 16 7
1 14
2 10 11
2 15 19
2 19 18
1 12
1 3
1 2
2 4 16
2 17 15

output:

17

result:

wrong answer 1st lines differ - expected: '16', found: '17'