• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# CF1610F F. Mashtali: a Space Oddysey

3小时前 1次浏览

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<list>
#define ll lonng long
#define N 600005

bool begin;

int n,m;

int to[N];
int from[N];

int sum[N];

int fans,ans[N];

int vis[N];

int cnt[N];

std::vector<int>Q[N][3];//边权为1，边权为2

int dfn[N];

bool end;

inline void dfs(int u,int now){
//	std::cout<<u<<" "<<now<<std::endl;
int fnow = now;
dfn[u] = 1;
while(head[u][3 - now] < Q[u][3 - now].size() && vis[Q[u][3 - now][head[u][3 - now]]])
//		std::cout<<Q[u][now].front()<<std::endl;
}else{
now = 3 - now;
//		std::cout<<Q[u][now].front()<<std::endl;
}
}
now = fnow;
}
return ;
}

int main(){
//	std::cout<<(&end - &begin) / 1024 / 1024<<std::endl;
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;++i){
int x,y,p;
scanf("%d%d%d",&x,&y,&p);
to[i] = x + y;
cnt[x] ++ ;
cnt[y] ++ ;
from[i] = x;
sum[x] += p;
sum[y] += p;
Q[x][p].push_back(i);
Q[y][p].push_back(i);
}
int mcnt = m;
for(int i = 1;i <= n;++i){
if(sum[i] & 1)
fans ++ ;
if(cnt[i] & 1){
int x = n + 1;
int y = i;
int p = 1;
to[++mcnt] = x + y;
from[mcnt] = x;
Q[x][p].push_back(mcnt);
Q[y][p].push_back(mcnt);
}
}
for(int i = 1;i <= n + 1;++i)
if(!dfn[i])
dfs(i,1);
std::cout<<fans<<std::endl;
for(int i = 1;i <= m;++i)
std::cout<<(ans[i]);
return 0;
}