oj.uz

Submission #255514

# Submission time Handle Problem Language Result Execution time Memory
255514 2020-08-01T07:08:10 Z b00n0rp Amusement Park (JOI17_amusement_park) C++17
100 / 100
 893 ms 13604 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define F first
#define S second

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

static const int MX = 10005;

static vi g[MX],adj[MX];
static int par[MX],dep[MX];

static bitset<MX> vis;
static int n,ind[MX];

static vi subgraph[MX];

static vi cc;

static void findtree(int u){
	// trace(u,cc.size());
	if(cc.size() < 60){
		ind[u] = cc.size();
		cc.pb(u);
	}
	vis[u] = 1;
	for(auto v:g[u]){
		if(!vis[v]){
			adj[u].pb(v);
			par[v] = u;
			dep[v] = 1+dep[u];
			findtree(v);
		}
	}
}

static void dfs(int u){
	if(ind[u] == -1){
		mii deg;
		for(auto x:subgraph[par[u]]){
			for(auto y:subgraph[par[u]]){
				if(binary_search(all(adj[x]),y)){
					deg[x]++;
					deg[y]++;
				}
			}
		}
		for(auto x:deg){
			if(x.S == 1 and x.F != par[u]){
				ind[u] = ind[x.F];
				for(auto y:subgraph[par[u]]){
					if(x.F != y) subgraph[u].pb(y);
				}
				subgraph[u].pb(u);
				break;
			}
		}
	}
	for(auto v:adj[u]){
		dfs(v);
	}
}

void Joi(int N, int M, int A[], int B[], long long X, int T){
	n = N;
	REP(i,M){
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}
	REP(i,n+2) ind[i] = -1;
	par[0] = 0;
	dep[0] = 0;
	findtree(0);
	for(auto x:cc) subgraph[x] = cc;
	REP(i,n) sort(all(adj[i]));
	dfs(0);
	REP(i,n) trace(i,ind[i],((X>>ind[i])&1));
	REP(i,n) MessageBoard(i,((X>>ind[i])&1));
}

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define F first
#define S second

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

static const int MX = 10005;

static vi g[MX],adj[MX];
static int par[MX],dep[MX];

static bitset<MX> vis;
static int n,ind[MX];

static vi subgraph[MX];

static vi cc;

static void findtree(int u){
	if(cc.size() < 60){
		ind[u] = cc.size();
		cc.pb(u);
	}
	vis[u] = 1;
	for(auto v:g[u]){
		if(!vis[v]){
			adj[u].pb(v);
			par[v] = u;
			dep[v] = 1+dep[u];
			findtree(v);
		}
	}
}

static void dfs(int u){
	if(ind[u] == -1){
		mii deg;
		for(auto x:subgraph[par[u]]){
			for(auto y:subgraph[par[u]]){
				if(binary_search(all(adj[x]),y)){
					deg[x]++;
					deg[y]++;
				}
			}
		}
		for(auto x:deg){
			if(x.S == 1 and x.F != par[u]){
				ind[u] = ind[x.F];
				for(auto y:subgraph[par[u]]){
					if(x.F != y) subgraph[u].pb(y);
				}
				subgraph[u].pb(u);
				break;
			}
		}
	}
	for(auto v:adj[u]){
		dfs(v);
	}
}

static long long ans = 0;

static void calc(int u){
	vis[u] = 1;
	for(auto v:adj[u]){
		if(vis[v]) continue;
		if(!binary_search(all(cc),v)) continue;
		ans |= (1LL<<ind[v])*Move(v);
		trace(v,ans);
		calc(v);
		ans |= (1LL<<ind[u])*Move(u);
		trace(u,ans);
	}
	int v = par[u];
	if(vis[v]) return;
	if(!binary_search(all(cc),v)) return;
	ans |= (1LL<<ind[v])*Move(v);
	trace(v,ans);
	calc(v);
	ans |= (1LL<<ind[u])*Move(u);
	trace(u,ans);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	n = N;
	REP(i,M){
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}
	REP(i,n+2) ind[i] = -1;
	par[0] = 0;
	dep[0] = 0;
	findtree(0);
	for(auto x:cc) subgraph[x] = cc;
	REP(i,n) sort(all(adj[i]));
	dfs(0);
	vis.reset();
	sort(all(subgraph[P]));
	cc = subgraph[P];
	calc(P);
	trace(ans);
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2180 KB Output is correct
2 Correct 9 ms 2568 KB Output is correct
3 Correct 17 ms 2520 KB Output is correct
4 Correct 4 ms 2184 KB Output is correct
5 Correct 5 ms 2560 KB Output is correct
6 Correct 10 ms 2312 KB Output is correct
7 Correct 20 ms 2448 KB Output is correct
8 Correct 10 ms 2320 KB Output is correct
9 Correct 14 ms 2524 KB Output is correct
10 Correct 7 ms 2440 KB Output is correct
11 Correct 11 ms 2820 KB Output is correct
12 Correct 2 ms 2184 KB Output is correct
13 Correct 16 ms 2516 KB Output is correct
14 Correct 16 ms 2320 KB Output is correct
15 Correct 17 ms 2512 KB Output is correct
16 Correct 17 ms 2512 KB Output is correct
17 Correct 19 ms 2512 KB Output is correct
18 Correct 16 ms 2512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 12272 KB Output is correct
2 Correct 749 ms 13296 KB Output is correct
3 Correct 743 ms 12952 KB Output is correct
4 Correct 731 ms 9832 KB Output is correct
5 Correct 673 ms 11568 KB Output is correct
6 Correct 873 ms 10820 KB Output is correct
7 Correct 873 ms 11292 KB Output is correct
8 Correct 852 ms 11508 KB Output is correct
9 Correct 813 ms 11272 KB Output is correct
10 Correct 376 ms 9704 KB Output is correct
11 Correct 355 ms 9712 KB Output is correct
12 Correct 600 ms 9032 KB Output is correct
13 Correct 604 ms 9440 KB Output is correct
14 Correct 626 ms 9704 KB Output is correct
15 Correct 655 ms 9932 KB Output is correct
16 Correct 639 ms 9888 KB Output is correct
17 Correct 707 ms 10056 KB Output is correct
18 Correct 720 ms 10012 KB Output is correct
19 Correct 734 ms 9956 KB Output is correct
20 Correct 436 ms 11656 KB Output is correct
21 Correct 403 ms 11424 KB Output is correct
22 Correct 846 ms 10640 KB Output is correct
23 Correct 847 ms 11208 KB Output is correct
24 Correct 850 ms 10968 KB Output is correct
25 Correct 851 ms 11124 KB Output is correct
26 Correct 866 ms 11236 KB Output is correct
27 Correct 862 ms 11412 KB Output is correct
28 Correct 844 ms 11032 KB Output is correct
29 Correct 761 ms 10388 KB Output is correct
30 Correct 806 ms 10772 KB Output is correct
31 Correct 8 ms 2564 KB Output is correct
32 Correct 10 ms 2312 KB Output is correct
33 Correct 10 ms 2520 KB Output is correct
34 Correct 7 ms 2312 KB Output is correct
35 Correct 5 ms 2320 KB Output is correct
36 Correct 3 ms 2324 KB Output is correct
37 Correct 3 ms 2212 KB Output is correct
38 Correct 2 ms 2184 KB Output is correct
39 Correct 2 ms 2216 KB Output is correct
40 Correct 4 ms 2312 KB Output is correct
41 Correct 5 ms 2440 KB Output is correct
42 Correct 3 ms 2184 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2180 KB Output is correct
2 Correct 3 ms 2568 KB Output is correct
3 Correct 3 ms 2312 KB Output is correct
4 Correct 61 ms 4072 KB Output is correct
5 Correct 61 ms 3892 KB Output is correct
6 Correct 61 ms 4056 KB Output is correct
7 Correct 59 ms 4056 KB Output is correct
8 Correct 61 ms 3892 KB Output is correct
9 Correct 365 ms 13524 KB Output is correct
10 Correct 372 ms 13604 KB Output is correct
11 Correct 383 ms 13228 KB Output is correct
12 Correct 2 ms 2336 KB Output is correct
13 Correct 2 ms 2184 KB Output is correct
14 Correct 2 ms 2312 KB Output is correct
15 Correct 3 ms 2312 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 12272 KB Output is correct
2 Correct 749 ms 12964 KB Output is correct
3 Correct 760 ms 12728 KB Output is correct
4 Correct 709 ms 9916 KB Output is correct
5 Correct 680 ms 12716 KB Output is correct
6 Correct 827 ms 11376 KB Output is correct
7 Correct 863 ms 11196 KB Output is correct
8 Correct 880 ms 10880 KB Output is correct
9 Correct 864 ms 10948 KB Output is correct
10 Correct 352 ms 9820 KB Output is correct
11 Correct 368 ms 9708 KB Output is correct
12 Correct 597 ms 9432 KB Output is correct
13 Correct 597 ms 9128 KB Output is correct
14 Correct 636 ms 9248 KB Output is correct
15 Correct 632 ms 10056 KB Output is correct
16 Correct 611 ms 9936 KB Output is correct
17 Correct 753 ms 9980 KB Output is correct
18 Correct 721 ms 9912 KB Output is correct
19 Correct 737 ms 9904 KB Output is correct
20 Correct 415 ms 11436 KB Output is correct
21 Correct 406 ms 11448 KB Output is correct
22 Correct 852 ms 10896 KB Output is correct
23 Correct 863 ms 11076 KB Output is correct
24 Correct 844 ms 10908 KB Output is correct
25 Correct 850 ms 11164 KB Output is correct
26 Correct 860 ms 11140 KB Output is correct
27 Correct 847 ms 11436 KB Output is correct
28 Correct 857 ms 10744 KB Output is correct
29 Correct 804 ms 10356 KB Output is correct
30 Correct 816 ms 10740 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 12632 KB Output is correct
2 Correct 758 ms 12928 KB Output is correct
3 Correct 750 ms 13112 KB Output is correct
4 Correct 726 ms 9776 KB Output is correct
5 Correct 705 ms 12960 KB Output is correct
6 Correct 877 ms 10788 KB Output is correct
7 Correct 885 ms 10904 KB Output is correct
8 Correct 828 ms 11356 KB Output is correct
9 Correct 863 ms 11248 KB Output is correct
10 Correct 395 ms 9708 KB Output is correct
11 Correct 393 ms 9744 KB Output is correct
12 Correct 623 ms 9208 KB Output is correct
13 Correct 649 ms 9448 KB Output is correct
14 Correct 619 ms 10004 KB Output is correct
15 Correct 766 ms 9984 KB Output is correct
16 Correct 643 ms 10180 KB Output is correct
17 Correct 741 ms 9884 KB Output is correct
18 Correct 728 ms 9884 KB Output is correct
19 Correct 736 ms 9772 KB Output is correct
20 Correct 413 ms 11436 KB Output is correct
21 Correct 412 ms 11424 KB Output is correct
22 Correct 836 ms 11036 KB Output is correct
23 Correct 853 ms 11176 KB Output is correct
24 Correct 848 ms 10792 KB Output is correct
25 Correct 856 ms 11100 KB Output is correct
26 Correct 883 ms 10892 KB Output is correct
27 Correct 893 ms 11412 KB Output is correct
28 Correct 863 ms 11664 KB Output is correct
29 Correct 771 ms 10772 KB Output is correct
30 Correct 812 ms 10784 KB Output is correct
31 Correct 8 ms 2564 KB Output is correct
32 Correct 9 ms 2552 KB Output is correct
33 Correct 9 ms 2448 KB Output is correct
34 Correct 7 ms 2564 KB Output is correct
35 Correct 4 ms 2560 KB Output is correct
36 Correct 3 ms 2320 KB Output is correct
37 Correct 2 ms 2312 KB Output is correct
38 Correct 2 ms 2184 KB Output is correct
39 Correct 2 ms 2332 KB Output is correct
40 Correct 6 ms 2312 KB Output is correct
41 Correct 5 ms 2312 KB Output is correct
42 Correct 2 ms 2208 KB Output is correct