제출 #199833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
199833		mohammedehab2002	Praktični (COCI18_prakticni)	C++11	130 / 130	172 ms	18936 KiB

parkticni

#include <bits/stdc++.h>
using namespace std;
bool vis[100005];
int a[100005],b[100005],c[100005],cum[100005],bas[30],ori[30],mask[30];
vector<pair<int,int> > v[100005];
vector<int> ans[100005];
void dfs(int node)
{
	vis[node]=1;
	for (auto u:v[node])
	{
		if (!vis[u.first])
		{
			cum[u.first]=(cum[node]^u.second);
			dfs(u.first);
		}
	}
}
int add(int a)
{
	int tmp=a,p=-1;
	for (int i=29;i>=0;i--)
	{
		if (tmp&(1<<i))
		tmp^=bas[i];
		if (p==-1 && tmp&(1<<i))
		p=i;
	}
	if (p==-1)
	return 0;
	bas[p]=tmp;
	ori[p]=a;
	for (int i=29;i>=0;i--)
	{
		if (p!=i && a&(1<<i))
		{
			a^=bas[i];
			mask[p]^=mask[i];
		}
	}
	mask[p]^=(1<<p);
	return 1;
}
int get(int a)
{
	int ret=0;
	for (int i=29;i>=0;i--)
	{
		if (a&(1<<i))
		{
			a^=bas[i];
			ret^=mask[i];
		}
	}
	return ret;
}
int main()
{
	int n,m,cnt=0;
	scanf("%d%d",&n,&m);
	for (int i=0;i<m;i++)
	{
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		v[a[i]].push_back({b[i],c[i]});
		v[b[i]].push_back({a[i],c[i]});
	}
	dfs(1);
	for (int i=0;i<m;i++)
	cnt+=add(cum[a[i]]^cum[b[i]]^c[i]);
	for (int i=0;i<m;i++)
	{
		int cur=get(cum[a[i]]^cum[b[i]]^c[i]);
		for (int j=0;j<30;j++)
		{
			if (cur&(1<<j))
			ans[j].push_back(i+1);
		}
	}
	printf("%d\n",cnt);
	for (int i=0;i<30;i++)
	{
		if (bas[i])
		{
			printf("%d %d",ori[i],ans[i].size());
			for (int j:ans[i])
			printf(" %d",j);
			printf("\n");
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

parkticni.cpp: In function 'int main()':
parkticni.cpp:84:39: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
    printf("%d %d",ori[i],ans[i].size());
                          ~~~~~~~~~~~~~^
parkticni.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
parkticni.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a[i],&b[i],&c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13