QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #308560 | #8018. 染色 | Evier | 0 | 3ms | 16112kb | C++14 | 3.9kb | 2024-01-20 10:29:33 | 2024-01-20 10:29:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define x first
#define y second
inline int read(){
int x=0;bool f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
if(f)return x;return ~(x-1);
}
const int inf=1e9;
int T,n,m,s,t,tot=1;
struct{
int nxt,to,w;
}e[5000005];
struct node{
int x,y,a,b;
// x前面边在不在匹配里 黑边奇偶性
};
int head[1005],now[1005],d[1005],x[250005],y[250005],c[1005][1005],a[1005][1005];
bool v[1005][1005],f[1005][1005][2][2],vis[1005][1005];
node pre[1005][1005][2][2];
vector<int> g1[1005],g2[1005];
inline void add(int u,int v,int w){
e[++tot].to=v,e[tot].nxt=head[u],e[tot].w=w,head[u]=tot;
e[++tot].to=u,e[tot].nxt=head[v],e[tot].w=0,head[v]=tot;
}
queue<int> q;
bool bfs(){
memset(d,0,sizeof(d));
while(!q.empty())q.pop();
q.push(s),d[s]=1,now[s]=head[s];
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(e[i].w&&!d[y]){
d[y]=d[x]+1,now[y]=head[y];
if(y==t)return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t)return flow;
int rest=flow,i;
for(i=now[x];i;i=e[i].nxt){
int y=e[i].to;
if(e[i].w&&d[y]==d[x]+1){
int k=dinic(y,min(e[i].w,rest));
if(!k)d[y]=0;
rest-=k;
e[i].w-=k,e[i^1].w+=k;
if(!rest)break;
}
}
now[x]=i;
return flow-rest;
}
queue<node> Q;
void out(node x){
int cnt=0;
while(1){
if(x.x==x.y)++cnt;
if(cnt==2)break;
node nw=pre[x.x][x.y][x.a][x.b];
if(nw.x!=x.x){
vis[x.x][nw.x]=vis[nw.x][x.x]=1;
if(!x.a)cout<<a[x.x][nw.x]<<" ";
}
x=nw;
}
}
bool solve(){
while(!Q.empty())Q.pop();
for(int i=1;i<=2*n;i++){
for(auto j:g1[i])Q.push({j,i,0,c[j][i]}),pre[j][i][0][c[j][i]]={i,i,0,0},f[j][i][0][c[j][i]]=1;
for(auto j:g2[i])Q.push({j,i,1,c[j][i]}),pre[j][i][1][c[j][i]]={i,i,0,0},f[j][i][1][c[j][i]]=1;
}
while(!Q.empty()){
node x=Q.front();Q.pop();
if(x.x==x.y&&x.b){
// cout<<x.x<<" "<<x.y<<" "<<x.a<<" "<<x.b<<"\n";
out(x);return 1;
}
if(x.a){
for(auto i:g1[x.x])if(!f[i][x.y][0][x.b^c[i][x.x]]){
f[i][x.y][0][x.b^c[i][x.x]]=1;
pre[i][x.y][0][x.b^c[i][x.x]]=x;
Q.push({i,x.y,0,x.b^c[i][x.x]});
}
}
else{
for(auto i:g2[x.x])if(!f[i][x.y][1][x.b^c[i][x.x]]){
f[i][x.y][1][x.b^c[i][x.x]]=1;
pre[i][x.y][1][x.b^c[i][x.x]]=x;
Q.push({i,x.y,1,x.b^c[i][x.x]});
}
}
}
return 0;
}
int main(){
T=read();
while(T--){
n=read(),m=read();
t=2*n+1,tot=1;
for(int i=0;i<=t;i++)head[i]=0,g1[i].clear(),g2[i].clear();
for(int i=1;i<=2*n;i++){
for(int j=1;j<=2*n;j++){
memset(f[i][j],0,sizeof(f[i][j]));
a[i][j]=0,c[i][j]=0,v[i][j]=0;vis[i][j]=0;
}
}
for(int i=1;i<=m;i++){
x[i]=read(),y[i]=read(),c[x[i]][y[i]]=read(),c[y[i]][x[i]]=c[x[i]][y[i]];
a[x[i]][y[i]]=a[y[i]][x[i]]=i;
add(x[i],y[i],1);
}
for(int i=1;i<=n;i++)add(s,i,1);
for(int i=n+1;i<=n<<1;i++)add(i,t,1);
int res=0;
while(bfs())res+=dinic(s,inf);
if(res!=n){
puts("-1");continue;
}
bool flag=0;
for(int i=1;i<=m;i++){
if(!e[i<<1].w){
g2[x[i]].push_back(y[i]),g2[y[i]].push_back(x[i]);
v[x[i]][y[i]]=v[y[i]][x[i]]=1;flag^=c[x[i]][y[i]];
// cout<<x[i]<<" "<<y[i]<<"\n";
}
else g1[x[i]].push_back(y[i]),g1[y[i]].push_back(x[i]);
}
if(!flag){
for(int i=1;i<=m;i++){
if(!e[i<<1].w)cout<<a[x[i]][y[i]]<<" ";
}
puts("");continue;
}
if(!solve()){
puts("-1");continue;
}
for(int i=1;i<=m;i++){
if(!e[i<<1].w&&!vis[x[i]][y[i]]){
cout<<a[x[i]][y[i]]<<" ";
}
}
puts("");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 16052kb
input:
2 0 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0
output:
-1
result:
wrong answer wa
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 11816kb
input:
2 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 1
output:
result:
wrong output format Unexpected end of file - int32 expected
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 15920kb
input:
2 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1
output:
-1 -1
result:
wrong answer wa
Test #4:
score: 0
Wrong Answer
time: 3ms
memory: 15848kb
input:
2 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0
output:
-1 -1
result:
wrong answer wa
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 16108kb
input:
4 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 0 1 ...
output:
-1
result:
wrong answer wa
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 11820kb
input:
4 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 ...
output:
-1 -1 -1
result:
wrong answer wa
Test #7:
score: 0
Wrong Answer
time: 2ms
memory: 15928kb
input:
4 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 ...
output:
-1 -1 -1 -1
result:
wrong answer wa
Test #8:
score: 0
Wrong Answer
time: 2ms
memory: 14024kb
input:
7 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 ...
output:
-1 -1 -1 -1 -1
result:
wrong answer wa
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 16112kb
input:
7 1 1 0 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 ...
output:
-1 -1 -1
result:
wrong answer wa
Test #10:
score: 0
Wrong Answer
time: 3ms
memory: 16052kb
input:
7 1 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 ...
output:
-1 -1 -1 -1 -1 -1
result:
wrong answer wa
Test #11:
score: 0
Wrong Answer
time: 2ms
memory: 14064kb
input:
11 1 1 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1...
output:
-1 -1 -1 -1 -1 -1
result:
wrong answer wa
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 15840kb
input:
11 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1...
output:
-1 -1 -1 -1 -1 -1
result:
wrong answer wa
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 15852kb
input:
11 1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0...
output:
-1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer wa
Test #14:
score: 0
Wrong Answer
time: 0ms
memory: 15808kb
input:
11 1 1 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 1...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer wa
Test #15:
score: 0
Wrong Answer
time: 0ms
memory: 13876kb
input:
11 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0...
output:
-1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer wa
Test #16:
score: 0
Wrong Answer
time: 0ms
memory: 15800kb
input:
11 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1...
output:
-1 -1 -1 -1 -1 -1
result:
wrong answer wa
Test #17:
score: 0
Wrong Answer
time: 0ms
memory: 15904kb
input:
11 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0...
output:
-1 -1 -1 -1 -1 -1 -1
result:
wrong answer wa
Test #18:
score: 0
Wrong Answer
time: 3ms
memory: 15848kb
input:
11 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1...
output:
-1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer wa
Test #19:
score: 0
Wrong Answer
time: 0ms
memory: 16112kb
input:
11 1 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 0...
output:
-1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer wa
Test #20:
score: 0
Wrong Answer
time: 0ms
memory: 15928kb
input:
11 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 0...
output:
-1 -1 -1 -1 -1
result:
wrong answer wa