QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#109419#6526. Canvaswtz2333WA 3ms26888kbC++174.7kb2023-05-28 22:57:302023-05-28 22:57:35

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-28 22:57:35]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:26888kb
  • [2023-05-28 22:57:30]
  • 提交

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::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::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[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);
    }
    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 << ' ';
    }
    for (auto i : ans2) std::cout << i << ' ';
    for (auto i : ans1) std::cout << i << ' ';
    for (auto i : ans3) std::cout << i << ' ';
    std::cout << '\n';
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
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: -100
Wrong Answer
time: 0ms
memory: 26884kb

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
1 2 3 4 5 8 13 7 6 11 10 9 12 

result:

wrong answer Participant's solution is incorrect. (test case 1)