QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110197#6526. CanvasFu_suRE 15ms3536kbC++175.5kb2023-06-01 03:11:302023-06-01 03:11:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-01 03:11:33]
  • 评测
  • 测评结果:RE
  • 用时:15ms
  • 内存:3536kb
  • [2023-06-01 03:11:30]
  • 提交

answer

#include "assert.h"
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>

const int maxn = 100;

int T;

struct OP {
  int l, x, r, y;
};

typedef long long int ll;
std::vector<std::pair<int, int>> e1[maxn];
bool ctrl[maxn];
int dfn[maxn], low[maxn], stk[maxn], ins[maxn], top, vistime, scnt, sz[maxn], bel[maxn], ind[maxn], c[maxn], inv[maxn], frstv[maxn], inid[maxn];

void clear() {
  for (auto &x : e1) x.clear();
#define clr(x) memset(x, 0, sizeof(x))
  clr(ctrl);
  clr(dfn);
  clr(low);
  clr(stk);
  clr(ins);
  clr(sz);
  clr(bel);
  clr(ind);
  clr(c);
  clr(inv);
  clr(frstv);
  clr(inid);
  top = vistime = scnt = 0;
}

void dfs(const int u) {
  low[u] = dfn[u] = ++vistime;
  ins[stk[++top] = u] = true;
  for (auto [v,id] : e1[u]) if (!ctrl[v] && dfn[v] == 0) {
    dfs(v);
    low[u] = std::min(low[u], low[v]);
  } else if (!ctrl[v] && ins[v]) {
    low[u] = std::min(low[u], low[v]);
  }
  if (low[u] == dfn[u]) {
    ++scnt; int v;
    do {
      ins[v = stk[top--]] = false;
      ++sz[bel[v] = scnt];
      frstv[scnt] = v;
    } while (u != v);
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  for (std::cin >> T; T; --T) {
    int n, m;
    std::cin >> n >> m;
    assert(std::max(n, m) <= 100);
    clear();
    std::vector<OP> op(m);
    std::vector<int> ans1, ans2, ans3, ans4;
    std::vector<int> prt(m + 1), vis(n + 1);
    for (int i = 0; i <= std::max(n, m); ++i) {
      e1[i].clear();
      ctrl[i] = false;
      dfn[i] = low[i] = stk[i] = ins[i] = bel[i] = sz[i] = ind[i] = c[i] = inv[i] = frstv[i] = inid[i] = 0;
    }
    top = vistime = scnt = 0;
    // e1 : 1->2, e2 : 2->1
    for (int i = 0; i < m; ++i) {
      OP &u = op[i];
      std::cin >> u.l >> u.x >> u.r >> u.y;
      if (u.x > u.y) {
        std::swap(u.x, u.y);
        std::swap(u.l, u.r);
      }
    }
    std::queue<int> Q;
    for (int u = 0; u < m; ++u) {
      OP i = op[u];
      int l = i.l, r = i.r;
      if (i.y == 2) {
        if (i.x == 1) {
          e1[l].push_back({r, u +1});
         // e2[r].push_back(l);
        } else {
          if (!ctrl[l]) {
            ctrl[l] = 1;
            Q.push(l);
          }
          if (!ctrl[r]) {
            ctrl[r] = 1;
            Q.push(r);
          }
          ans3.push_back(1 + u);
        }
      }
    }
    for (int u; !Q.empty(); Q.pop()) {
      u = Q.front();
      for (auto [v, id] : e1[u]) if (!ctrl[v]) {
        ans1.push_back(id);
        ctrl[v] = 1;
        Q.push(v);
      }
    }
    std::reverse(ans1.begin(), ans1.end());
    for (int i = 1; i <= n; ++i) if (!ctrl[i] && dfn[i] == 0) {
      dfs(i);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) if (!ctrl[i]) {
      for (auto [v,id] : e1[i]) if (!ctrl[v] && bel[i] != bel[v]) {
        ++ind[bel[v]]; inv[bel[v]] = v; inid[bel[v]] = id;
      }
    }
    for (int i = 1; i <= n; ++i) if (!ctrl[i]) {
      for (auto [v, id] : e1[i]) if (!ctrl[v]) {
        if (c[i] < 1) {
          ++ans;
          c[i] = 1;
        }
        if (c[v] < 2) {
          ans += 2 - c[v];
          c[v] = 2;
        }
      }
    }
    for (int i = 1; i <= scnt; ++i) if (!ind[i] && sz[i] > 1) {
      --ans;
    }
    for (int i = 1; i <= n; ++i) if (ctrl[i]) {
      c[i] = 2;
      ans += 2;
    }
    for (auto i : op) if ((i.y == 1) || (i.x == 1 && ctrl[i.r])) {
      if (c[i.l] == 0) {
        c[i.l] = 1;
        ++ans;
      }
      if (c[i.r] == 0) {
        c[i.r] = 1;
        ++ans;
      }
    }
    std::cout << ans << '\n';
  /*  for (int i = 0; i < m; ++i) {
      OP u = op[i];
      if (u.y == 1) {
       // ans1.push_back(i + 1);
       // prt[i + 1] = true;
      }
    }*/
    for (int i = 1; i <= scnt; ++i) if (inv[i]) {
    //  std::cerr << i << '\n';
      std::vector<int> tmp;
      vis[inv[i]] = 1;
      for (Q.push(inv[i]); !Q.empty(); Q.pop()) {
        
        for (auto [v, id] : e1[Q.front()]) if (bel[v] == i && vis[v] == 0) {
          tmp.push_back(id);
          Q.push(v);
          vis[v] = 1;
        }
      }
      std::reverse(tmp.begin(), tmp.end());
      for (auto u : tmp) ans2.push_back(u);
      ans2.push_back(inid[i]);
    } else if (sz[i] != 1) {
   //   std::cerr << frstv[i] << '\n';
     // std::cerr << ans2.size() << '\n';
      std::vector<int> tmp;
      vis[frstv[i]] = 1;
      for (Q.push(frstv[i]); !Q.empty(); Q.pop()) {
        for (auto [v, id] : e1[Q.front()]) if (bel[v] == i && vis[v] == 0) {
       //   std::cerr << Q.front() << ' ' << v << ' ' << id << '\n';
          tmp.push_back(id);
          Q.push(v);
          vis[v] = 1;
        } else {
       //   std::cerr << Q.front() << ' ' << v << '\n';
        }
      }
      std::reverse(tmp.begin(), tmp.end());
      for (auto u : tmp) ans2.push_back(u);
    }
    for (auto i : ans2) prt[i] = true;
    for (auto i : ans1) prt[i] = true;
    for (auto i : ans3) prt[i] = true;
    for (int i = 1; i <= m; ++i) if (prt[i] == false) {
      std::cout << i << ' ';
    }
   // return 0;
    for (auto i : ans2) std::cout << i << ' ';
    for (auto i : ans1) std::cout << i << ' ';
    for (auto i : ans3) std::cout << i << ' ';
    std::cout << '\n';
  }
}
/**********************************************************************
	Problem: 1011
	User: team010
	Language: C++
	Result: RE
**********************************************************************/

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3436kb

input:

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

output:

7
2 4 1 3 
5
2 1 

result:

ok Correct. (2 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3432kb

input:

1
10 13
1 1 2 2
2 1 3 2
1 2 3 1
3 1 4 2
4 1 5 2
5 1 6 2
4 2 6 1
7 1 8 2
8 1 9 2
7 2 9 1
5 2 9 1
8 2 10 2
1 1 10 1

output:

19
3 4 5 8 13 2 1 7 6 11 10 9 12 

result:

ok Correct. (1 test case)

Test #3:

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

input:

1
7 5
2 1 6 2
1 2 6 1
1 1 5 1
2 2 7 1
1 1 7 2

output:

8
2 3 1 4 5 

result:

ok Correct. (1 test case)

Test #4:

score: 0
Accepted
time: 2ms
memory: 3492kb

input:

1
7 6
2 1 7 2
2 1 4 2
1 2 4 1
2 1 6 1
1 1 6 2
2 2 6 1

output:

9
3 4 1 2 6 5 

result:

ok Correct. (1 test case)

Test #5:

score: 0
Accepted
time: 2ms
memory: 3436kb

input:

1
7 5
5 2 7 1
5 1 6 2
3 2 7 1
3 2 6 1
6 1 7 2

output:

7
1 4 3 5 2 

result:

ok Correct. (1 test case)

Test #6:

score: 0
Accepted
time: 2ms
memory: 3536kb

input:

1
7 6
1 2 5 1
2 1 7 2
1 2 7 1
2 2 7 1
1 1 5 2
1 2 3 1

output:

8
1 4 6 5 3 2 

result:

ok Correct. (1 test case)

Test #7:

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

input:

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

output:

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

result:

ok Correct. (2000 test cases)

Test #8:

score: 0
Accepted
time: 15ms
memory: 3476kb

input:

2000
15 18
10 1 15 2
10 1 15 2
3 2 13 1
5 1 6 2
2 1 10 2
3 2 5 2
7 1 12 2
2 2 3 1
12 1 13 2
5 2 11 1
7 1 15 2
5 1 15 2
6 1 11 2
2 1 6 1
5 1 10 2
5 2 10 1
2 1 7 2
2 1 15 2
15 17
7 2 15 1
6 2 10 1
3 2 12 1
13 2 14 1
1 1 7 2
6 2 15 1
6 2 13 2
1 2 6 1
10 2 15 1
12 2 15 1
9 1 10 2
13 1 15 2
9 2 12 1
3 1 ...

output:

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

result:

ok Correct. (2000 test cases)

Test #9:

score: 0
Accepted
time: 2ms
memory: 3500kb

input:

5
27 33
18 2 23 1
13 1 23 2
2 1 7 2
4 2 7 1
2 1 4 2
9 1 27 2
26 2 27 1
3 2 11 1
2 1 4 2
12 1 18 2
4 2 7 1
25 2 26 1
12 1 17 2
5 1 27 2
5 2 22 1
13 2 25 1
2 1 4 2
4 2 7 1
2 2 26 1
4 2 7 1
2 2 7 1
2 2 17 1
19 1 26 1
3 2 24 1
11 1 24 2
3 2 24 1
3 1 9 2
18 1 22 2
9 1 11 2
5 2 23 2
12 2 17 1
2 2 7 1
4 2 ...

output:

33
2 4 5 6 8 9 10 11 15 17 18 20 21 22 23 24 26 31 32 25 29 27 13 3 16 19 12 28 7 33 1 14 30 
37
3 5 7 8 9 10 14 19 20 21 22 25 6 4 17 13 2 16 24 27 26 28 1 11 18 15 23 12 
38
2 3 5 7 12 15 16 20 21 22 24 25 26 27 28 30 31 32 33 34 23 6 14 11 29 35 10 4 9 13 19 18 8 1 36 17 
34
2 4 5 7 9 10 12 13 14...

result:

ok Correct. (5 test cases)

Test #10:

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

input:

5
27 37
10 2 25 2
18 2 22 1
18 1 22 2
2 1 24 2
14 2 26 1
4 1 27 2
15 2 25 1
24 1 27 2
7 2 20 1
11 1 18 1
2 1 14 2
15 1 25 2
10 2 15 1
9 1 16 2
24 2 27 1
24 1 27 2
10 2 12 1
10 1 15 2
9 2 14 1
6 1 15 2
7 1 27 2
24 1 27 2
6 1 22 2
16 1 20 2
15 1 24 2
4 1 27 2
24 1 27 2
2 1 4 2
24 2 27 1
7 1 26 2
24 1 ...

output:

35
3 4 5 6 7 8 10 12 13 15 16 17 20 21 22 23 26 27 29 31 32 35 36 2 33 30 9 24 14 19 11 28 37 34 25 18 1 
37
6 7 8 10 11 16 17 20 22 23 26 27 28 29 30 31 32 19 18 3 21 4 25 34 14 33 15 13 12 9 2 24 5 1 
35
1 2 11 12 13 14 17 18 19 21 22 23 25 26 27 29 33 34 10 5 15 32 7 16 31 20 6 24 4 8 9 30 3 28 
...

result:

ok Correct. (5 test cases)

Test #11:

score: -100
Dangerous Syscalls

input:

200
739 1933
110 1 669 2
17 2 403 1
39 1 538 2
36 2 267 1
66 2 259 1
55 2 483 1
245 2 450 1
30 1 729 2
318 1 568 2
344 1 681 2
11 2 37 1
15 2 192 1
55 2 344 1
426 2 596 1
3 2 683 1
499 1 614 1
302 1 367 2
220 1 528 1
223 2 563 1
255 2 719 1
153 2 688 1
371 2 648 1
704 2 715 1
367 2 477 1
451 2 698 2...

output:


result: