oj.uz

Submission #553935

# Submission time Handle Problem Language Result Execution time Memory
553935 2022-04-27T11:30:02 Z nafis_shifat Amusement Park (JOI17_amusement_park) C++17
0 / 100
 25 ms 19916 KB 
#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);

	}
}

void prc() {
	for(int i = 0; i < n; i++) {
		if(!done[i] || bit[i]) continue;
		
		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;

			for(int j = 0; j < rem; j++) {
				con[id].push_back(con[group[i]][j]);
			}

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



	for(int i = 0; i < n; i++) {
		if(!done[i] || bit[i] != SZ - 1) continue;

		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;

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

			for(int j = SZ - rem; j < SZ; j++) {
				con[id].push_back(con[group[i]][j]);
			}

			
		}
	}
}
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 = 0; i < n; i++) {
		assert(done[i]);
		MessageBoard(i, ((X >> bit[i]) & 1));
	}
}

#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);

		}
	}

	void prc() {
		for(int i = 0; i < n; i++) {
			if(!done[i] || bit[i]) continue;
			
			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;

				for(int j = 0; j < rem; j++) {
					con[id].push_back(con[group[i]][j]);
				}

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



		for(int i = 0; i < n; i++) {
			if(!done[i] || bit[i] != SZ - 1) continue;

			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;

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

				for(int j = SZ - rem; j < SZ; j++) {
					con[id].push_back(con[group[i]][j]);
				}

				
			}
		}
	}

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

	void get_ans(int u, int prev) {

		for(int v : adj[u]) {
			if(v == prev || !allowed[v]) continue;

			int 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();

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

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

	cc.get_ans(P, -1);

	return cc.ans;



}

Compilation message

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:85:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   85 |     assert(Vis.size() < SZ);
      |            ~~~~~~~~~~~^~~~
Ioi.cpp:118:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  118 |     assert(Vis.size() < SZ);
      |            ~~~~~~~~~~~^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 14804 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 19908 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 16516 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 19856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 19916 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -