oj.uz

Submission #92038

# Submission time Handle Problem Language Result Execution time Memory
92038 2019-01-01T09:08:01 Z bharat2002 Praktični (COCI18_prakticni) C++14
26 / 130
 139 ms 18760 KB 
/*input
4 5
1 2 3
2 3 4
2 4 8
1 3 0
1 4 0
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 100;
const int mod=1e9 + 7;
#define int long long
class pii 
{	
public:
	int f, s, ind;
};
inline pii mp(int a, int b, int c)
{
	pii t;t.f=a;t.s=b;t.ind=c;return t;
}
inline pair<int, int> makep(int a, int b)
{
	pair<int, int> t;t.first=a;t.second=b;return t;
}
vector< pii > adjlist[N];int n, m;
vector< pair<int, int> > req;bool visited[N];int xval[N];
vector<int> queries[40];int qvals[40];
void dfs(int i, int p)
{
	visited[i]=1;
	for(auto j:adjlist[i])
	{
		if(visited[j.f]&&j.f!=p)
		{
			if((j.s^xval[i]^xval[j.f])==0||i>j.f) continue;
			req.push_back(make_pair(j.ind, (j.s^xval[i]^xval[j.f])));continue;
		}
		else if(!visited[j.f])
		{
			xval[j.f]=(xval[i]^j.s);dfs(j.f, i);
		}
	}
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u, v, w;cin>>u>>v>>w;adjlist[u].push_back(mp(v, w, i));adjlist[v].push_back(mp(u, w, i));
	}
	for(int i=1;i<=n;i++)
	{
		visited[i]=xval[i]=0;
	}
	dfs(1, -1);
	if(req.empty())
	{
		cout<<0;return 0;
	}
	int ans=0;
	for(int i=29;i>=0;i--)
	{
		qvals[ans]=0;stack<int> upind;
		for(int ft=0;ft<req.size();ft++)
		{
			auto j=req[ft];
			if((j.second&(1<<i))) {queries[ans].push_back(j.first);upind.push(ft);qvals[ans]|=j.second;}
		}
		while(!upind.empty()) {int cur=upind.top();req[cur].second^=qvals[ans];upind.pop();}
		if(qvals[ans]==0)
		{
			queries[ans].clear();continue;
		}
		ans++;
	}
	cout<<ans<<endl;
	for(int i=0;i<ans;i++)
	{
		cout<<qvals[i]<<" "<<queries[i].size()<<" ";
		for(auto j:queries[i]) cout<<j<<" ";cout<<endl;
	}
}

Compilation message

parkticni.cpp: In function 'int main()':
parkticni.cpp:56:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   visited[i]=xval[i]=0;
              ~~~~~~~^~
parkticni.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int ft=0;ft<req.size();ft++)
                ~~^~~~~~~~~~~
parkticni.cpp:83:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(auto j:queries[i]) cout<<j<<" ";cout<<endl;
   ^~~
parkticni.cpp:83:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(auto j:queries[i]) cout<<j<<" ";cout<<endl;
                                       ^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8060 KB Output is correct
2 Correct 34 ms 8056 KB Output is correct
3 Correct 10 ms 4088 KB Output is correct
4 Correct 10 ms 4088 KB Output is correct
5 Correct 82 ms 13532 KB Output is correct
6 Correct 100 ms 12664 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5312 KB Output is correct
2 Correct 16 ms 5116 KB Output is correct
3 Correct 21 ms 5852 KB Output is correct
4 Correct 24 ms 6520 KB Output is correct
5 Correct 68 ms 12768 KB Output is correct
6 Correct 39 ms 8948 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 9592 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 12612 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 11384 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 17104 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 12920 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 18760 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 5880 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 14240 KB Too many operations
2 Halted 0 ms 0 KB -