oj.uz

Submission #199833

# Submission time Handle Problem Language Result Execution time Memory
199833 2020-02-03T14:54:30 Z mohammedehab2002 Praktični (COCI18_prakticni) C++11
130 / 130
 172 ms 18936 KB 
#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");
		}
	}
}

Compilation message

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 8824 KB Output is correct
2 Correct 49 ms 9208 KB Output is correct
3 Correct 16 ms 5880 KB Output is correct
4 Correct 17 ms 6012 KB Output is correct
5 Correct 112 ms 13560 KB Output is correct
6 Correct 111 ms 12920 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6776 KB Output is correct
2 Correct 28 ms 6904 KB Output is correct
3 Correct 32 ms 7548 KB Output is correct
4 Correct 36 ms 7932 KB Output is correct
5 Correct 92 ms 12408 KB Output is correct
6 Correct 61 ms 9592 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 9976 KB Output is correct
2 Correct 79 ms 11512 KB Output is correct
3 Correct 9 ms 4984 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 12432 KB Output is correct
2 Correct 143 ms 16632 KB Output is correct
3 Correct 10 ms 5112 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 10744 KB Output is correct
2 Correct 95 ms 11816 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 13304 KB Output is correct
2 Correct 54 ms 9468 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 13048 KB Output is correct
2 Correct 129 ms 15504 KB Output is correct
3 Correct 99 ms 11768 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 16760 KB Output is correct
2 Correct 172 ms 18936 KB Output is correct
3 Correct 154 ms 18296 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7676 KB Output is correct
2 Correct 47 ms 8456 KB Output is correct
3 Correct 110 ms 13692 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 13948 KB Output is correct
2 Correct 64 ms 10360 KB Output is correct
3 Correct 151 ms 17272 KB Output is correct