QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#143420 | #6526. Canvas | MaxBlazeResFire | WA | 10ms | 27384kb | C++23 | 2.9kb | 2023-08-21 11:19:43 | 2023-08-21 11:19:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 500005
int n,m,Vis[MAXN];
struct node{
int u,x,v,y;
node(){}
node( int a , int b , int c , int d ): u(a),x(b),v(c),y(d){}
}N[MAXN];
vector< pair<int,int> > E[MAXN],P;
vector<int> Ans,Scc[MAXN];
int dfn[MAXN],low[MAXN],idx,st[MAXN],top,inst[MAXN];
int Scnt,bel[MAXN],deg[MAXN],vis[MAXN],col[MAXN];
int sta[MAXN];
void tarjan( int x ){
dfn[x] = low[x] = ++idx,inst[x] = 1,st[++top] = x;
for( pair<int,int> p : E[x] ){
int v = p.first;
if( !dfn[v] ) tarjan( v ),low[x] = min( low[x] , low[v] );
else if( inst[v] ) low[x] = min( low[x] , dfn[v] );
}
if( dfn[x] == low[x] ){
Scnt ++;
while( st[top] != x ){
int v = st[top];
bel[v] = Scnt,inst[v] = 0,Scc[Scnt].emplace_back( v );
top --;
}
bel[x] = Scnt,inst[x] = 0,Scc[Scnt].emplace_back( x );
top --;
}
}
int Ansvis[MAXN];
void get_ans( int x ){
for( pair<int,int> p : E[x] ){
int v = p.first,w = p.second;
if( !Ansvis[w] ) Ansvis[w] = 1,Ans.emplace_back( w ),get_ans( v );
}
}
int cc[MAXN];
inline void solve(){
scanf("%lld%lld",&n,&m);
for( int i = 1 ; i <= m ; i ++ ){
int u,x,v,y; scanf("%lld%lld%lld%lld",&u,&x,&v,&y);
N[i] = node( u , x , v , y );
if( x == 2 && y == 2 ) P.emplace_back( make_pair( u , v ) ),Ans.emplace_back( i );
if( x == 1 && y == 2 ) E[u].emplace_back( make_pair( v , i ) ),Vis[u] = Vis[v] = 1;
if( y == 1 && x == 2 ) E[v].emplace_back( make_pair( u , i ) ),Vis[v] = Vis[u] = 1;
}
for( int i = 1 ; i <= n ; i ++ ) if( !dfn[i] && Vis[i] ) tarjan( i );
for( int u = 1 ; u <= n ; u ++ ){
for( pair<int,int> p : E[u] ){
int v = p.first;
if( bel[u] != bel[v] ) if( !vis[bel[v]] ) deg[bel[v]] ++,vis[bel[v]] = 1;
}
for( pair<int,int> p : E[u] ){
int v = p.first;
vis[bel[v]] = 0;
}
}
for( pair<int,int> ele : P ){
int u = ele.first,v = ele.second;
col[bel[u]] = col[bel[v]] = 1;
sta[bel[u]] = u,sta[bel[v]] = v;
}
int Ansc = 0;
for( int i = 1 ; i <= Scnt ; i ++ )
if( !deg[i] && !col[i] ) sta[i] = Scc[i][0];
for( int i = 1 ; i <= Scnt ; i ++ ) if( !deg[i] ) get_ans( sta[i] );
for( int i = 1 ; i <= m ; i ++ )
if( N[i].x == 1 && N[i].y == 1 ) Ans.emplace_back( i );
reverse( Ans.begin() , Ans.end() );
for( int r : Ans ){
int u = N[r].u,v = N[r].v;
Ansc -= cc[u],Ansc -= cc[v];
cc[u] = N[r].x,cc[v] = N[r].y;
Ansc += cc[u],Ansc += cc[v];
}
printf("%lld\n",Ansc);
for( int ele : Ans ) printf("%lld ",ele); puts("");
for( int i = 1 ; i <= n ; i ++ ) dfn[i] = low[i] = st[i] = inst[i] = cc[i] = bel[i] = vis[i] = Vis[i] = col[i] = deg[i] = sta[i] = Ansvis[i] = 0;
for( int i = 1 ; i <= n ; i ++ ) E[i].clear(); P.clear(); Ans.clear();
for( int i = 1 ; i <= Scnt ; i ++ ) Scc[i].clear();
idx = top = Scnt = 0;
}
signed main(){
int testcase; scanf("%lld",&testcase);
while( testcase -- ) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 27376kb
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: 0
Accepted
time: 1ms
memory: 27156kb
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 13 11 8 10 9 7 6 5 4 2 1 3 12
result:
ok Correct. (1 test case)
Test #3:
score: 0
Accepted
time: 5ms
memory: 27144kb
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 3 1 4 5 2
result:
ok Correct. (1 test case)
Test #4:
score: 0
Accepted
time: 5ms
memory: 27168kb
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 4 2 1 6 5 3
result:
ok Correct. (1 test case)
Test #5:
score: 0
Accepted
time: 5ms
memory: 27120kb
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 3 5 4 2 1
result:
ok Correct. (1 test case)
Test #6:
score: 0
Accepted
time: 0ms
memory: 27344kb
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 6 2 4 1 5 3
result:
ok Correct. (1 test case)
Test #7:
score: -100
Wrong Answer
time: 10ms
memory: 27384kb
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 7 6 4 16 8 11 15 9 13 14 10 2 5 1 3 12 20 14 11 15 1 13 10 9 8 12 3 5 7 6 2 4 21 2 11 13 6 10 3 9 12 7 8 4 1 14 5 18 7 9 10 14 13 12 6 4 8 3 1 5 11 2 21 6 11 14 10 7 2 13 3 19 18 9 12 17 8 4 5 1 15 21 3 6 2 11 7 12 13 8 9 14 5 4 10 1 21 3 14 8 1 5 2 11 9 7 15 6 13 4 12 10 19 11 7 10 9 14 6...
result:
wrong answer Integer parameter [name=p_i] equals to 21, violates the range [1, 19] (test case 5)