QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#153513 | #6526. Canvas | qzez | WA | 10ms | 30344kb | C++14 | 2.3kb | 2023-08-30 09:26:48 | 2023-08-30 09:26:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=5e5+10;
int T,n,m,use[N],col[N];
struct opts{
int l,x,r,y;
}a[N];
vector<pair<int,int> >to[N];
#define v e.first
#define w e.second
int k,ans[N],vis[N];
void dfs(int u){
if(vis[u])return;
vis[u]=1;
for(auto e:to[u]){
ans[++k]=w;
dfs(v);
}
}
int sct,dft,top,scc[N],dfn[N],low[N],stk[N],in[N];
void tarjan(int u){
low[u]=dfn[u]=++dft,stk[++top]=u;
for(auto e:to[u])if(!vis[v]){
if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
else if(!scc[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
sct++;
do scc[stk[top]]=sct;while(stk[top--]^u);
}
}
void build(){
for(int u=1;u<=n;u++)if(!vis[u]){
for(auto e:to[u])if(!vis[v]){
if(scc[u]^scc[v])in[scc[v]]++;
}
}
}
#undef v
#undef w
void get(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&a[i].l,&a[i].x,&a[i].r,&a[i].y);
if(a[i].x+a[i].y==3){
if(a[i].x==1)to[a[i].l].push_back({a[i].r,i});
else to[a[i].r].push_back({a[i].l,i});
}
}
for(int i=1;i<=m;i++){
if(a[i].x+a[i].y==4){
ans[++k]=i;
dfs(a[i].l),dfs(a[i].r);
}
}
for(int i=1;i<=n;i++)if(!dfn[i]&&!vis[i])tarjan(i);
build();
for(int i=1;i<=n;i++)if(!vis[i]&&!in[scc[i]])dfs(i);
for(int i=1;i<=k;i++)use[ans[i]]=1;
for(int i=1;i<=m;i++){
if(!use[i])ans[++k]=i;
}
reverse(ans+1,ans+1+k);
int res=0;
// debug("ans",ary(ans,1,k));
for(int i=1;i<=k;i++){
col[a[ans[i]].l]=a[ans[i]].x;
col[a[ans[i]].r]=a[ans[i]].y;
}
// debug("col",ary(col,1,n));
printf("%d\n",accumulate(col+1,col+1+n,0));
for(int i=1;i<=k;i++)printf("%d%c",ans[i],"\n "[i<k]);
}
void clr(){
dft=sct=k=top=0;
for(int i=1;i<=n;i++){
to[i].clear();
dfn[i]=col[i]=low[i]=vis[i]=in[i]=0;
}
for(int i=1;i<=m;i++){
use[i]=0;
}
}
int main(){
for(scanf("%d",&T);T--;clr())get();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 30256kb
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: 28240kb
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 4 3 2 1 5 7 6 11 8 10 9 12
result:
ok Correct. (1 test case)
Test #3:
score: 0
Accepted
time: 8ms
memory: 28296kb
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 2 1 4 5
result:
ok Correct. (1 test case)
Test #4:
score: 0
Accepted
time: 2ms
memory: 30344kb
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 3 2 1 6 5
result:
ok Correct. (1 test case)
Test #5:
score: 0
Accepted
time: 3ms
memory: 28144kb
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 1 5 4 2
result:
ok Correct. (1 test case)
Test #6:
score: 0
Accepted
time: 0ms
memory: 28212kb
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 4 1 5 3 2
result:
ok Correct. (1 test case)
Test #7:
score: -100
Wrong Answer
time: 10ms
memory: 30196kb
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 8 11 3 15 9 1 13 14 10 2 5 6 4 16 12 20 14 15 3 1 13 10 9 8 12 11 6 2 5 7 4 21 2 11 13 6 10 3 9 12 7 14 8 4 1 5 17 11 7 5 1 9 3 13 4 8 12 6 10 14 2 17 19 18 16 14 13 12 11 10 9 7 6 3 2 1 5 17 8 4 15 21 6 3 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 14 11 9 5 3 2 16 1...
result:
wrong answer Jury has better answer. Participant 17, jury 18 (test case 4)