QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#643412#6526. CanvashongrockWA 10ms60912kbC++173.3kb2024-10-15 21:03:262024-10-15 21:03:27

Judging History

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

  • [2024-10-15 21:03:27]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:60912kb
  • [2024-10-15 21:03:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define pb emplace_back
#define mp make_pair

using ll = long long;
using pii = pair<int,int>;

constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr int N = 5e5 + 10;

int T, n, m, a[N], deg[N], deg2[N];
int l[N], x[N], r[N], y[N];
bool done[N], vis[N];
vector<int> pre, ext;
vector<pii> V[N], G[N];
vector<int> S[N];
int low[N], dfn[N], dfs_cnt;
int scc_num, scc[N];
int st[N], top;
bool in_stk[N], has_out[N];

void dfs(int u){
  low[u] = dfn[u] = ++dfs_cnt;
  st[top++] = u;
  in_stk[u] = 1;
  for(auto [to, id] : V[u]){
    if(!dfn[to]){
      dfs(to);
      low[u] = min(low[u], low[to]);
    } else if(in_stk[to]){
      low[u] = min(low[u], dfn[to]);
    }
  }
  if(dfn[u] == low[u]){
    ++scc_num;
    while(true){
      --top;
      scc[st[top]] = scc_num;
      S[scc_num].pb(st[top]);
      in_stk[st[top]] = 0;
      if(st[top] == u)  break;
    }
  }
}

void update(int id){
  vis[id] = 1;
  ext.pb(id);
}

void dfs2(int x){
  deg2[x] = 0;
  for(auto [to, id] : V[x]){
    if(!vis[id] && scc[to] == scc[x]){
      update(id);
      if(deg2[to] != 0) dfs2(to);
    }
  }
}

void solve(int u){
  for(int x : S[u]){
    deg2[x] = 1;
  }
  for(int x : S[u]){
    if(done[x] || has_out[x]){
      dfs2(x);
      return;
    }
  }
  dfs2(S[u][0]);
}

void _main(){
  cin >> T;
  while(T--){
    pre.clear();
    ext.clear();
    cin >> n >> m;
    for(int i=1; i<=m; ++i){
      cin >> l[i] >> x[i] >> r[i] >> y[i];
      if(x[i] == 1 && y[i] == 1){
        pre.pb(i);
        vis[i] = 1;
      } else if(x[i] == 2 && y[i] == 2){
        vis[i] = 1;
        ext.pb(i);
        done[l[i]] = done[r[i]] = 1;
      } else {
        if(x[i] == 1){
          V[l[i]].pb(r[i], i);
        } else {
          V[r[i]].pb(l[i], i);
        }
      }
    }

    queue<int> Q;
    scc_num = 0;
    dfs_cnt = 0;
    for(int i=1; i<=n; ++i){
      if(!dfn[i]){
        top = 0;
        dfs(i);
      }
    }

    for(int i=1; i<=n; ++i){
      int x = scc[i];
      has_out[i] = 0;
      for(auto [to, id] : V[i]){
        if(x != scc[to]){
          ++deg[scc[to]];
          has_out[i] = 1;
          G[x].pb(scc[to], id);
        }
      }
    }

    for(int i=1; i<=scc_num; ++i){
      if(deg[i] == 0){
        Q.push(i);
      }
    }
    while(!Q.empty()){
      int x = Q.front(); Q.pop();
      solve(x);

      for(auto [to, id] : G[x]){
        update(id);
        if(--deg[to] == 0){
          Q.push(to);
        }
      }
    }

    reverse(ext.begin(), ext.end());
    pre.insert(pre.end(), ext.begin(), ext.end());
    for(int i=1; i<=n; ++i){
      a[i] = 0;
    }
    for(auto id : pre){
      a[l[id]] = x[id];
      a[r[id]] = y[id];
    }

    int sum = 0;
    for(int i=1; i<=n; ++i){
      sum += a[i];
    }
    cout << sum << '\n';
    for(int i=0; i<m; ++i){
      cout << pre[i] << " \n"[i == m - 1];
    }

    for(int i=1; i<=n; ++i){
      V[i].clear();
      G[i].clear();
      done[i] = 0;
      low[i] = dfn[i] = 0;
      in_stk[i] = 0;
      deg[i] = 0;
      S[i].clear();
    }
    for(int i=1; i<=m; ++i){
      vis[i] = 0;
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  _main();
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 10ms
memory: 59176kb

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
4 2 1 3
5
2 1

result:

ok Correct. (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 60912kb

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:

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

result:

wrong answer Jury has better answer. Participant 17, jury 19 (test case 1)