Submission #33223

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
33223	2017-10-23T03:56:33 Z	model_code	Simurgh (IOI17_simurgh)	C++11	51 / 100	196 ms	22828 KB

simurgh

/*
   	IOI 2017
	Problem: Finding Spanning Tree
	Author: PrinceOfPersia
	Subtask: 3
*/
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include "simurgh.h"
using namespace std;
#define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
#define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
#define rep(i, c) for(auto &(i) : (c))
#define x first
#define y second
#define pb push_back
#define PB pop_back()
#define iOS ios_base::sync_with_stdio(false)
#define sqr(a) (((a) * (a)))
#define all(a) a.begin() , a.end()
#define error(x) cerr << #x << " = " << (x) <<endl
#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define umap unordered_map
#define double long double
typedef long long ll;
typedef pair<int,int>pii;
typedef vector<int> vi;
template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
template <class T>	inline void sminmax(T &mn, T &mx, T x){smin(mn, x), smax(mx, x);}
const int maxn = 512, maxm = maxn * maxn / 2;
bool mark[maxn];
int h[maxn], ind[maxn][maxn], par[maxn], n, m, state[maxm], last_num[maxm];
int __edges[maxn];
vi __edges_vec;
vi adj[maxn];
pii edges[maxm];
bool bit[maxm];
int _next_ = 1;
int _last_id[maxm];
inline void _renew(){
	vi __edges_new;
	rep(i, __edges_vec)	if(bit[i] && _last_id[i] != _next_)
		__edges_new.pb(i), _last_id[i] = _next_;
	++ _next_;
	__edges_vec = __edges_new;
}
vi __ans;
inline int query(){
	_renew();
	int res = count_common_roads(__edges_vec);
	if(res == n-1)
		__ans = __edges_vec;
	return res;
}
inline void toggle(int i){
	if(!bit[i]){
		bit[i] = true;
		__edges_vec.pb(i);
	}
	else
		bit[i] = false;
}
inline void reset(){
	while(!__edges_vec.empty()){
		int e = __edges_vec.back();
		__edges_vec.PB;
		bit[e] = false;
	}
}
vi back_edges[maxn];
inline void dfs(int v = 0, int p = -1){
	if(~p)	h[v] = h[p] + 1;
	mark[v] = true;
	par[v] = p;
	rep(u, adj[v])
		if(!mark[u])
			dfs(u, v);
	if(~p)
		toggle(ind[v][p]);
}
int tree_score;
inline void DFS(int v = 0){
	rep(u, adj[v]){
		if(v == par[u])
			DFS(u);
		else if(u != par[v] && h[u] < h[v]){
			int e = ind[v][u];
			int cur = v;
			while(cur != u){
				back_edges[cur].pb(e);
				cur = par[cur];
			}
		}
	}
	if(~par[v]){
		int e2p = ind[v][par[v]];
		int for_a_one = -1, mn = tree_score, mx = mn;
		last_num[e2p] = tree_score;
		toggle(e2p);
		rep(e, back_edges[v]){
			if(min(for_a_one, state[e]) == -1){
				toggle(e);
				last_num[e] = query();
				if(~state[e])
					for_a_one = last_num[e] + (!state[e]);
				sminmax(mn, mx, last_num[e]);
				toggle(e);
			}
		}
		toggle(e2p);
		smax(mx, for_a_one);
		state[e2p] = tree_score == mx;
		rep(e, back_edges[v])	if(state[e] == -1)
			state[e] = last_num[e] == mx;
	}
	
}
vi find_roads(int n, vi v, vi u){
	::n = n;
	m = v.size();
	memset(ind, -1, sizeof ind);
	memset(state, -1, sizeof state);
	For(i,0,m){
		edges[i] = {v[i], u[i]};
		ind[v[i]][u[i]] = ind[u[i]][v[i]] = i;
		adj[v[i]].pb(u[i]), adj[u[i]].pb(v[i]);
	}
	dfs();
	tree_score = query();
	DFS();
	reset();
	For(i,0,m)	if(state[i] == 1)
		toggle(i);
	query();
	return __ans;
}

Subtask #1
13.0 / 13.0

#	Verdict	Memory	Grader output
1	Correct	5772 KB	correct
2	Correct	5772 KB	correct
3	Correct	5772 KB	correct
4	Correct	5772 KB	correct
5	Correct	5772 KB	correct
6	Correct	5772 KB	correct
7	Correct	5772 KB	correct
8	Correct	5772 KB	correct
9	Correct	5772 KB	correct
10	Correct	5772 KB	correct
11	Correct	5772 KB	correct
12	Correct	5772 KB	correct
13	Correct	5772 KB	correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	5772 KB	correct
2	Correct	0 ms	5772 KB	correct
3	Correct	0 ms	5772 KB	correct
4	Correct	0 ms	5772 KB	correct
5	Correct	0 ms	5772 KB	correct
6	Correct	0 ms	5772 KB	correct
7	Correct	0 ms	5772 KB	correct
8	Correct	0 ms	5772 KB	correct
9	Correct	0 ms	5772 KB	correct
10	Correct	0 ms	5772 KB	correct
11	Correct	0 ms	5772 KB	correct
12	Correct	0 ms	5772 KB	correct
13	Correct	0 ms	5772 KB	correct
14	Correct	3 ms	5904 KB	correct
15	Correct	3 ms	5904 KB	correct
16	Correct	3 ms	5904 KB	correct
17	Correct	3 ms	5904 KB	correct
18	Correct	0 ms	5904 KB	correct
19	Correct	0 ms	5904 KB	correct
20	Correct	3 ms	5904 KB	correct
21	Correct	3 ms	5904 KB	correct
22	Correct	3 ms	5904 KB	correct
23	Correct	0 ms	5772 KB	correct
24	Correct	0 ms	5772 KB	correct
25	Correct	0 ms	5772 KB	correct
26	Correct	0 ms	5772 KB	correct
27	Correct	0 ms	5772 KB	correct
28	Correct	0 ms	5772 KB	correct
29	Correct	0 ms	5772 KB	correct
30	Correct	0 ms	5904 KB	correct
31	Correct	0 ms	5904 KB	correct
32	Correct	0 ms	5904 KB	correct
33	Correct	0 ms	5904 KB	correct

Subtask #3
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	5772 KB	correct
2	Correct	0 ms	5772 KB	correct
3	Correct	0 ms	5772 KB	correct
4	Correct	0 ms	5772 KB	correct
5	Correct	0 ms	5772 KB	correct
6	Correct	0 ms	5772 KB	correct
7	Correct	0 ms	5772 KB	correct
8	Correct	0 ms	5772 KB	correct
9	Correct	0 ms	5772 KB	correct
10	Correct	0 ms	5772 KB	correct
11	Correct	0 ms	5772 KB	correct
12	Correct	0 ms	5772 KB	correct
13	Correct	0 ms	5772 KB	correct
14	Correct	3 ms	5904 KB	correct
15	Correct	3 ms	5904 KB	correct
16	Correct	3 ms	5904 KB	correct
17	Correct	3 ms	5904 KB	correct
18	Correct	0 ms	5904 KB	correct
19	Correct	0 ms	5904 KB	correct
20	Correct	3 ms	5904 KB	correct
21	Correct	3 ms	5904 KB	correct
22	Correct	3 ms	5904 KB	correct
23	Correct	0 ms	5772 KB	correct
24	Correct	0 ms	5772 KB	correct
25	Correct	0 ms	5772 KB	correct
26	Correct	0 ms	5772 KB	correct
27	Correct	0 ms	5772 KB	correct
28	Correct	0 ms	5772 KB	correct
29	Correct	0 ms	5772 KB	correct
30	Correct	0 ms	5904 KB	correct
31	Correct	0 ms	5904 KB	correct
32	Correct	0 ms	5904 KB	correct
33	Correct	0 ms	5904 KB	correct
34	Correct	173 ms	18836 KB	correct
35	Correct	163 ms	18732 KB	correct
36	Correct	106 ms	15952 KB	correct
37	Correct	6 ms	6168 KB	correct
38	Correct	179 ms	18980 KB	correct
39	Correct	153 ms	17968 KB	correct
40	Correct	116 ms	16000 KB	correct
41	Correct	196 ms	18800 KB	correct
42	Correct	186 ms	18944 KB	correct
43	Correct	83 ms	10288 KB	correct
44	Correct	69 ms	8708 KB	correct
45	Correct	73 ms	9264 KB	correct
46	Correct	59 ms	8264 KB	correct
47	Correct	26 ms	6300 KB	correct
48	Correct	3 ms	5772 KB	correct
49	Correct	6 ms	5904 KB	correct
50	Correct	19 ms	6300 KB	correct
51	Correct	86 ms	9264 KB	correct
52	Correct	63 ms	8704 KB	correct
53	Correct	56 ms	8260 KB	correct
54	Correct	83 ms	10296 KB	correct
55	Correct	89 ms	12352 KB	correct
56	Correct	83 ms	12200 KB	correct
57	Correct	93 ms	12332 KB	correct

Subtask #4
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	5772 KB	correct
2	Correct	0 ms	5772 KB	correct
3	Incorrect	149 ms	22828 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	5772 KB	correct
2	Correct	0 ms	5772 KB	correct
3	Correct	0 ms	5772 KB	correct
4	Correct	0 ms	5772 KB	correct
5	Correct	0 ms	5772 KB	correct
6	Correct	0 ms	5772 KB	correct
7	Correct	0 ms	5772 KB	correct
8	Correct	0 ms	5772 KB	correct
9	Correct	0 ms	5772 KB	correct
10	Correct	0 ms	5772 KB	correct
11	Correct	0 ms	5772 KB	correct
12	Correct	0 ms	5772 KB	correct
13	Correct	0 ms	5772 KB	correct
14	Correct	3 ms	5904 KB	correct
15	Correct	3 ms	5904 KB	correct
16	Correct	3 ms	5904 KB	correct
17	Correct	3 ms	5904 KB	correct
18	Correct	0 ms	5904 KB	correct
19	Correct	0 ms	5904 KB	correct
20	Correct	3 ms	5904 KB	correct
21	Correct	3 ms	5904 KB	correct
22	Correct	3 ms	5904 KB	correct
23	Correct	0 ms	5772 KB	correct
24	Correct	0 ms	5772 KB	correct
25	Correct	0 ms	5772 KB	correct
26	Correct	0 ms	5772 KB	correct
27	Correct	0 ms	5772 KB	correct
28	Correct	0 ms	5772 KB	correct
29	Correct	0 ms	5772 KB	correct
30	Correct	0 ms	5904 KB	correct
31	Correct	0 ms	5904 KB	correct
32	Correct	0 ms	5904 KB	correct
33	Correct	0 ms	5904 KB	correct
34	Correct	173 ms	18836 KB	correct
35	Correct	163 ms	18732 KB	correct
36	Correct	106 ms	15952 KB	correct
37	Correct	6 ms	6168 KB	correct
38	Correct	179 ms	18980 KB	correct
39	Correct	153 ms	17968 KB	correct
40	Correct	116 ms	16000 KB	correct
41	Correct	196 ms	18800 KB	correct
42	Correct	186 ms	18944 KB	correct
43	Correct	83 ms	10288 KB	correct
44	Correct	69 ms	8708 KB	correct
45	Correct	73 ms	9264 KB	correct
46	Correct	59 ms	8264 KB	correct
47	Correct	26 ms	6300 KB	correct
48	Correct	3 ms	5772 KB	correct
49	Correct	6 ms	5904 KB	correct
50	Correct	19 ms	6300 KB	correct
51	Correct	86 ms	9264 KB	correct
52	Correct	63 ms	8704 KB	correct
53	Correct	56 ms	8260 KB	correct
54	Correct	83 ms	10296 KB	correct
55	Correct	89 ms	12352 KB	correct
56	Correct	83 ms	12200 KB	correct
57	Correct	93 ms	12332 KB	correct
58	Correct	0 ms	5772 KB	correct
59	Correct	0 ms	5772 KB	correct
60	Incorrect	149 ms	22828 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

Submission #33223

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0