QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#109474#6526. CanvasFu_suML 8ms27000kbC++175.2kb2023-05-29 09:45:042023-05-29 09:45:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-29 09:45:07]
  • 评测
  • 测评结果:ML
  • 用时:8ms
  • 内存:27000kb
  • [2023-05-29 09:45:04]
  • 提交

answer

#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>

const int maxn = 1000005;

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 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;
    std::vector<OP> op(m);
    std::vector<int> ans1, ans2, ans3, ans4;
    std::vector<int> prt(m + 1), vis(n + 1);
    for (int i = 1; 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[i] == 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: 8ms
memory: 26888kb

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: 4ms
memory: 26980kb

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: 4ms
memory: 26900kb

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: 0ms
memory: 26928kb

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: 7ms
memory: 26952kb

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: 6ms
memory: 27000kb

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 5 6 3 2 

result:

ok Correct. (1 test case)

Test #7:

score: -100
Memory Limit Exceeded

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:


result: