Submission #553994

#	Time	Username	Problem	Language	Result	Execution time	Memory
553994		nafis_shifat	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	319 ms	23812 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;

vector<int> g[mxn];
vector<int> adj[mxn];
int n;
int vis[mxn] = {};
const int SZ = 60;
void dfs0(int u) {
	vis[u] = 1;
	for(int v : g[u]) {
		if(vis[v]) continue;
		adj[u].push_back(v);
		adj[v].push_back(u);
		dfs0(v);
	}
}



int bit[mxn] = {};
int group[mxn] = {};
vector<int> con[mxn];

int id = 0;
int done[mxn] = {};


vector<int> dfs(int u, int prev) {

	vector<int> cur;

	cur.push_back(u);
	for(int v : adj[u]) {
		if(v == prev) continue;
		vector<int> x = dfs(v, u);

		for(int i : x) cur.push_back(i);
	}


    if(cur.size() < SZ) return cur;
    id++;
    for(int i = 0; i < SZ; i++) {
    	group[cur[i]] = id;
    	bit[cur[i]] = i;
    	con[id].push_back(cur[i]);
    	done[cur[i]] = 1;
    }

    return {};
}


vector<int> Vis;
void travel(int u, int prev) {
	Vis.push_back(u);
	done[u] = 1;
	for(int v : adj[u]) {
		if(v == prev || done[v]) continue;
		travel(v, u);

	}
}

bool na[mxn] = {};

vector<int> na_con;

void dfs2(int u, int prev) {
	na_con.push_back(u);
	for(int v : adj[u]) {
		if(v == prev || !na[v]) continue;
		dfs2(v, u);
	}
} 

void prc() {
	for(int i = 0; i < n; i++) {
		if(!done[i]) continue;

		for(int j : con[group[i]]) na[j] = 1;
		
		for(int u : adj[i]) {
			if(done[u]) continue;

			id++;
	

			Vis.clear();
			travel(u, -1);

			assert(Vis.size() < SZ);



			int sz = Vis.size();
			int rem = SZ - sz;


			na_con.clear();
			dfs2(i, -1);

			set<int> bt;
			for(int j = 0; j < SZ; j++) bt.insert(j);

			for(int j = 0; j < rem; j++) {
				bt.erase(bit[na_con[j]]);
				con[id].push_back(na_con[j]);

			}

			for(int j = 0; j < sz; j++) {
				con[id].push_back(Vis[j]);
				bit[Vis[j]] = *bt.begin();
				bt.erase(bt.begin());
				group[Vis[j]] = id;
				done[Vis[j]] = 1;
			}			
		}

		for(int j : con[group[i]]) na[j] = 0;
		
	}


}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	n = N;
	for(int i = 0; i < M; i++) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}

	dfs0(0);

	dfs(0, -1);
	prc();

	// for(int i = 1; i <= id; i++) {
	// 	cout<<"GROUP "<<i<<":   ";
	// 	for(int j : con[i]) cout<<j<<" ";
	// 	cout<<endl;
	// }



	for(int i = 0; i < n; i++) {
		assert(done[i]);
		
		MessageBoard(i, ((X >> bit[i]) & 1));
	}
}

Ioi

#include "Ioi.h"

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;

struct CON {
	vector<int> g[mxn];
	vector<int> adj[mxn];
	int n;
	int vis[mxn] = {};
	const int SZ = 60;
	void dfs0(int u) {
		vis[u] = 1;
		for(int v : g[u]) {
			if(vis[v]) continue;
			adj[u].push_back(v);
			adj[v].push_back(u);
			dfs0(v);
		}
	}


	int bit[mxn] = {};
	int group[mxn] = {};
	vector<int> con[mxn];

	int id = 0;
	int done[mxn] = {};


	vector<int> dfs(int u, int prev) {

		vector<int> cur;

		cur.push_back(u);
		for(int v : adj[u]) {
			if(v == prev) continue;
			vector<int> x = dfs(v, u);

			for(int i : x) cur.push_back(i);
		}


	    if(cur.size() < SZ) return cur;
	    id++;
	    for(int i = 0; i < SZ; i++) {
	    	group[cur[i]] = id;
	    	bit[cur[i]] = i;
	    	con[id].push_back(cur[i]);
	    	done[cur[i]] = 1;
	    }

	    return {};
	}


	vector<int> Vis;
	void travel(int u, int prev) {
		Vis.push_back(u);
		done[u] = 1;
		for(int v : adj[u]) {
			if(v == prev || done[v]) continue;
			travel(v, u);

		}
	}

	bool na[mxn] = {};

	vector<int> na_con;

	void dfs2(int u, int prev) {
		na_con.push_back(u);
		for(int v : adj[u]) {
			if(v == prev || !na[v]) continue;
			dfs2(v, u);
		}
	} 

	void prc() {
		for(int i = 0; i < n; i++) {
			if(!done[i]) continue;

			for(int j : con[group[i]]) na[j] = 1;
			
			for(int u : adj[i]) {
				if(done[u]) continue;

				id++;
				// cout<<"NEW GROUP FROM start "<<i<<" Index "<<id<<endl;



				Vis.clear();
				travel(u, -1);

				assert(Vis.size() < SZ);



				int sz = Vis.size();
				int rem = SZ - sz;


				na_con.clear();
				dfs2(i, -1);

				set<int> bt;
				for(int j = 0; j < SZ; j++) bt.insert(j);

				for(int j = 0; j < rem; j++) {
					bt.erase(bit[na_con[j]]);
					con[id].push_back(na_con[j]);
				}

				for(int j = 0; j < sz; j++) {
					con[id].push_back(Vis[j]);
					bit[Vis[j]] = *bt.begin();
					bt.erase(bt.begin());
					group[Vis[j]] = id;
					done[Vis[j]] = 1;
				}			
			}

			for(int j : con[group[i]]) na[j] = 0;
			
		}


	}

	ll ans = 0;
	bool allowed[mxn] = {};

	void get_ans(int u, int prev) {

		for(int v : adj[u]) {
			if(v == prev || !allowed[v]) continue;
			ll x = Move(v);
			ans |= (x << bit[v]);
			get_ans(v, u);

		}

		if(prev != -1) Move(prev);
	}	
} cc;

bool allowed[mxn] = {};

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	cc.n = N;
	for(int i = 0; i < M; i++) {
		cc.g[A[i]].push_back(B[i]);
		cc.g[B[i]].push_back(A[i]);
	}
	cc.dfs0(0);
	cc.dfs(0, -1);
	cc.prc();

	ll v = V;
	cc.ans |= v << (cc.bit[P]);

	for(int i = 0; i < cc.SZ; i++) {
		cc.allowed[cc.con[cc.group[P]][i]] = 1;
		// cout<<cc.con[cc.group[P]][i]<<" ";
	}
	// cout<<endl;

	cc.get_ans(P, -1);



	return cc.ans;



}

Compilation message (stderr)

Ioi.cpp: In member function 'std::vector<int> CON::dfs(int, int)':
Ioi.cpp:48:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   48 |      if(cur.size() < SZ) return cur;
      |         ~~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Ioi.cpp:3:
Ioi.cpp: In member function 'void CON::prc()':
Ioi.cpp:101:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  101 |     assert(Vis.size() < SZ);
      |            ~~~~~~~~~~~^~~~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17