QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#109484 | #6526. Canvas | KING_OF_TURTLE | WA | 1ms | 3524kb | C++14 | 1.9kb | 2023-05-29 11:20:47 | 2023-05-29 11:20:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mk make_pair
#define lowbit(x) (x&(-x))
#define pb emplace_back
#define pr pair<int,int>
#define let const auto
#define all(A) A.begin(),A.end()
void chkmin(int &x,int y){x=min(x,y);}
void chkmax(int &x,int y){x=max(x,y);}
const int N=5e5+5;
int read(){
int x=0,f=1; char c=getchar();
while(('0'>c||c>'9')&&c!='-') c=getchar();
if(c=='-') f=0,c=getchar();
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?x:-x;
}
void solve(){
vector <int> ans;
int n=read(),m=read();
vector <int> vis(n,0),vs(n,0);
vector <int> both;
vector <int> fir,Mx(n,0),Mn(n,1);
vector <vector<pr> > to(n);
for(int i=1; i<=m; i++){
int a=read()-1,b=read()-1,c=read()-1,d=read()-1;
vis[a]=vis[c]=1;
Mn[a]=min(Mn[a],b);Mn[c]=min(Mn[c],d);
chkmax(Mx[a],b),chkmax(Mx[c],d);
if(b&&d){
vs[a]=vs[c]=1;
both.pb(i);
}
else if(b||d){
if(b) swap(a,c);
to[a].pb(c,i);
}
else fir.pb(i);
}
for(int i=0; i<n; i++) if(!Mx[i])
for(auto &[u,v]:to[i]) vs[u]=1,both.pb(v);
queue <int> q;
for(int i=0; i<n; i++)
if(vs[i]) q.push(i);
auto bfs = [&](){
while(!q.empty()){
int u=q.front(); q.pop();
for(auto &[v,id]:to[u]){
ans.pb(id);
if(!vs[v]) vs[v]=1,q.push(v);
}
}
};
bfs();
int p=0,res=0;
while(p<n){
while(p<n&&(vs[p]||Mx[p]==0)) p++;
if(p>=n) break;
q.push(p),vs[p]=1;
bfs();
p++; res++;
}
for(int i=0;i<n;++i)if(Mn[i]==1&&vis[i])--res;
printf("%d\n",accumulate(all(vis),0)+accumulate(all(vs),0)-res);
// assert(fir.size()+ans.size()+both.size()==m);
for(int i:fir) printf("%d ",i);
reverse(ans.begin(),ans.end());
for(int i:ans)
printf("%d ",i);
for(int i:both)
printf("%d ",i);
puts("");
}
int main(){
int T=read();
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3524kb
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:
8 4 1 3 2 6 2 1
result:
wrong answer Participant's solution is incorrect. (test case 1)