oj.uz

Submission #97052

# Submission time Handle Problem Language Result Execution time Memory
97052 2019-02-13T14:21:19 Z hjc20032003 Praktični (COCI18_prakticni) C++14
130 / 130
 245 ms 13304 KB 
#include<bits/stdc++.h>
#define REP(i,s,t) for(int i=s;i<=t;i++) 
#define mp make_pair
#define A first
#define B second
#define TO e[i].to
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
const int maxn=2e5+5;
struct Edge {int nxt,to,val;}e[maxn];
int hd[maxn],e_cnt;
void add(int u,int v,int val) {
	e[++e_cnt]=(Edge){hd[u],v,val};
	hd[u]=e_cnt;
}
int px[maxn],dfn[maxn],bad_cnt;
pii bad[maxn];
void dfs(int u,int d,int x) {
	dfn[u]=d; px[u]=x;
	for(int i=hd[u];i;i=e[i].nxt) {
		if(!dfn[TO]) dfs(TO,d+1,x^e[i].val);
		else if(dfn[TO]<d-1) {
			int tx=x^e[i].val^px[TO];
			if(tx) bad[++bad_cnt]=mp(i,tx);
		}
	}
}
int cnt,ans[50];
vector<int> vec[50];
int main() {
	int n,m; cin>>n>>m;
	REP(i,1,m) {
		int a,b,p; cin>>a>>b>>p;
		add(a,b,p); add(b,a,p);
	}
	dfs(1,1,0);
	REP(i,0,29) {
		int id=0;
		REP(j,1,bad_cnt) if(bad[j].B&1<<i) id=j;
		if(!id) continue;
		ans[++cnt]=bad[id].B;
		REP(j,1,bad_cnt) if(bad[j].B&1<<i) bad[j].B^=ans[cnt],vec[cnt].pb(bad[j].A);
	}
	cout<<cnt<<'\n';
	REP(i,1,cnt) {
		cout<<ans[i]<<' '<<vec[i].size()<<' ';
		sort(vec[i].begin(),vec[i].end());
		for(int j=0;j<vec[i].size();j++) cout<<((vec[i][j]-1)>>1)+1<<' ';
		cout<<'\n';
	}
	return 0;
}

Compilation message

parkticni.cpp: In function 'int main()':
parkticni.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<vec[i].size();j++) cout<<((vec[i][j]-1)>>1)+1<<' ';
               ~^~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 3704 KB Output is correct
2 Correct 70 ms 4064 KB Output is correct
3 Correct 22 ms 1144 KB Output is correct
4 Correct 15 ms 1280 KB Output is correct
5 Correct 124 ms 7416 KB Output is correct
6 Correct 149 ms 7928 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1892 KB Output is correct
2 Correct 36 ms 1824 KB Output is correct
3 Correct 67 ms 2504 KB Output is correct
4 Correct 73 ms 2840 KB Output is correct
5 Correct 118 ms 6876 KB Output is correct
6 Correct 75 ms 4344 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 4624 KB Output is correct
2 Correct 109 ms 5836 KB Output is correct
3 Correct 3 ms 384 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 6592 KB Output is correct
2 Correct 234 ms 10956 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 5436 KB Output is correct
2 Correct 117 ms 5752 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 7864 KB Output is correct
2 Correct 75 ms 4088 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 7224 KB Output is correct
2 Correct 165 ms 9232 KB Output is correct
3 Correct 116 ms 6008 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 10648 KB Output is correct
2 Correct 245 ms 13304 KB Output is correct
3 Correct 205 ms 11868 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2424 KB Output is correct
2 Correct 61 ms 3348 KB Output is correct
3 Correct 170 ms 8084 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 8020 KB Output is correct
2 Correct 78 ms 4728 KB Output is correct
3 Correct 193 ms 10872 KB Output is correct