QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#643417 | #6526. Canvas | hongrock | WA | 4ms | 58940kb | C++17 | 3.3kb | 2024-10-15 21:05:10 | 2024-10-15 21:05:11 |
Judging History
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]){
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];
for(auto [to, id] : V[i]){
if(x != scc[to]){
++deg[scc[to]];
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: 4ms
memory: 58940kb
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: 0ms
memory: 58892kb
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:
18 13 6 5 7 11 8 10 9 4 2 1 3 12
result:
wrong answer Jury has better answer. Participant 18, jury 19 (test case 1)