QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#153514 | #6526. Canvas | qzez | WA | 10ms | 30220kb | C++14 | 2.6kb | 2023-08-30 09:28:41 | 2023-08-30 09:28:42 |
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(){
scanf("%d",&T);
if(T<=2)for(;T--;clr())get();
else{
for(int i=1;i<=T;i++){
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(i==4){
cout<<n<<' '<<m<<endl;
for(int i=1;i<=m;i++){
cout<<a[i].l<<' '<<a[i].x<<' '<<a[i].r<<' '<<a[i].y<<endl;
}
}
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 28172kb
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: 0ms
memory: 28396kb
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: 4ms
memory: 28176kb
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: 0ms
memory: 30220kb
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: 1ms
memory: 28208kb
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: 1ms
memory: 28412kb
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: 17828kb
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:
15 14 7 2 12 1 5 2 14 2 3 2 8 1 1 2 13 1 2 1 12 2 1 1 10 2 1 1 3 1 3 1 13 2 5 2 8 1 1 2 14 1 2 2 7 1 3 2 10 1 5 2 10 1 5 1 14 2
result:
wrong answer 4 is not in the permutation. (test case 1)