Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 讨论区数据全过了就是WA，这么难受的吗

Posted by zhuiyicc at 2018-08-06 21:03:53 on Problem 1417
```#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
#define maxn 100 + 10
#define INF 0x3f3f3f3f
#define ll long long
int fa[1205],r[1205],a[1205],b[1205],p[1205];
int dp[705][2][705],pre[705][2][705];
struct edge{
int x[2];
int id;
}c[1205];
int getroot(int x){
if(fa[x] == x) return x;
int t = getroot(fa[x]);
r[x] = r[x] ^ r[fa[x]];
return fa[x] = t;
}
void uniontree(int x,int y,int z){
int fx = getroot(x);
int fy = getroot(y);
if(fx != fy){
fa[fy] = fx;
if(!z) r[fy] = r[x] ^ r[y];
else r[fy] = (r[x] == r[y]);
if(r[fy]) a[fx] += b[fy],b[fx] += a[fy];
else a[fx] += a[fy],b[fx] += b[fy];
}
}
void init(int n){
for(int i = 1;i <= n;++i){
fa[i] = i;
a[i] = 1,b[i] = 0;
r[i] = 0;
}
}
/*
4 4 1
1 2 yes
2 3 yes
4 1 no
5 1 yes

6 2 6
1 2 no
3 5 yes
2 5 yes
6 1 yes
3 4 yes
4 5 yes

6 3 5
1 3 yes
4 5 yes
1 2 no
2 5 yes
6 3 yes
2 3 no

*/
int main(){
int n,p1,p2,x,y;
char s[5];
while(~scanf("%d%d%d",&n,&p1,&p2)){
if(!n && !p1 && !p2) break;
int m = p1 + p2;
init(m);
for(int i = 0;i < n;++i){
scanf("%d%d%s",&x,&y,s);
if(s[0] == 'n') uniontree(x,y,1);
else uniontree(x,y,0);
}
int len = 0;
for(int i = 1;i <= m;++i){
if(fa[i] == i){
c[len].x[0] = a[i];
c[len].x[1] = b[i];
c[len].id = i;
len++;
}
}
memset(dp,0,sizeof(dp));
memset(pre,0,sizeof(pre));
dp[0][0][c[0].x[0]] = 1;
dp[0][1][c[0].x[1]] = 1;
for(int i = 1;i < len;++i){
for(int j = 0;j < 2;++j){
for(int k = c[i].x[j];k <= p1;++k){
if(dp[i - 1][0][k - c[i].x[j]]){
dp[i][j][k] += dp[i - 1][0][k - c[i].x[j]];
pre[i][j][k] = 0;
}
if(dp[i - 1][1][k - c[i].x[j]]){
dp[i][j][k] += dp[i - 1][1][k - c[i].x[j]];
pre[i][j][k] = 1;
}
}
}
}
if(p1 == p2 || dp[len - 1][0][p1] + dp[len - 1][1][p1] >= 2 || dp[len - 1][0][p1] + dp[len - 1][1][p1] == 0){
puts("no");
continue;
}
int leng = 0;
if(dp[len - 1][0][p1]){
int t = 0;
for(int i = len - 1;i >= 0;--i){
for(int j = 1;j <= m;++j){
int fx = getroot(j);
if(fx == c[i].id && r[j] == t) p[leng++] = j;
}
t = pre[i][t][p1];
if(!t) p1 -= c[i].x[0];
else p1 -= c[i].x[1];
}
}
else if(dp[len - 1][1][p1]){
int t = 1;
for(int i = len - 1;i >= 0;--i){
for(int j = 1;j <= m;++j){
int fx = getroot(j);
if(fx == c[i].id && r[j] == t) p[leng++] = j;
}
t = pre[i][t][p1];
if(!t) p1 -= c[i].x[0];
else p1 -= c[i].x[1];
}
}
sort(p,p + leng);
for(int i = 0;i < leng;++i){
printf("%d\n",p[i]);
}
puts("end");
}
return 0;
}```

Followed by: