Submission #1215054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215054		dyj133446	OGLEDALA (COI15_ogledala)	C++20	0 / 100	1 ms	576 KiB

ogledala

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,k,c[N],cnt[N],u[N],v[N],w[N],p[N],p1[N],p2[N];
bool flag[N],vis[N];
vector<int>v1[N];
vector<pair<int,int>>e[N];
int getfa(int x)
{
	if(p[x]==x)return x;
	return p[x]=getfa(p[x]);
}
void add(int x)
{
	e[u[x]].emplace_back(v[x],x),e[v[x]].emplace_back(u[x],x);
	cnt[w[x]]++,flag[x]=1;
}
void Erase(int x,pair<int,int>y)
{
	auto it=e[x].begin();
	while(it!=e[x].end())
	{
		if((*it)==y)return e[x].erase(it),void();
		it++;
	}
}
void del(int x)
{
	cnt[w[x]]--,flag[x]=0;
	Erase(u[x],make_pair(v[x],x));
	Erase(v[x],make_pair(u[x],x));
}
void dfs(int x,int prt)
{
	p1[x]=prt;
	for(auto y:e[x])if(y.first!=prt)p2[y.first]=y.second,dfs(y.first,x);
}
vector<int>Get(int x,int y)
{
	dfs(x,0);
	vector<int>res;
	while(y!=x)res.emplace_back(p2[y]),y=p1[y];
	return res;
}
bool solve(int x)
{
	vis[x]=1;
	for(auto y:v1[x])if(!flag[y])
	{
		int fx=getfa(u[y]),fy=getfa(v[y]);
		if(fx!=fy)
		{
			p[fy]=fx,add(y);
			return true;
		}
		vector<int>t=Get(u[y],v[y]);
		for(auto i:t)if(!vis[w[i]])
		{
			del(i),add(y);
			if(solve(w[i]))return true;
			add(i),del(y);
		}
	}
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++)cin>>c[i];
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i]>>w[i];
		v1[w[i]].emplace_back(i);
	}
	for(int i=1;i<=n;i++)p[i]=i;
	for(int i=1;i<=k;i++)
	{
		while(cnt[i]<c[i])
		{
			memset(vis,0,sizeof(vis));
			if(!solve(i))break;
		}
	}
	int ans=0;
	for(int i=1;i<=k;i++)ans+=cnt[i];
	cout<<m-ans<<'\n';
	for(int i=1;i<=m;i++)if(!flag[i])cout<<i<<' ';
	return 0;
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59