oj.uz

답안 #553963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
553963 2022-04-27T12:27:36 Z nafis_shifat Amusement Park (JOI17_amusement_park) C++17
0 / 100
 49 ms 22960 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);

	}
}

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

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

	// cout<<"HERE NO: "<<cc.group[P]<<endl;
	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

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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 16536 KB Output is correct
2 Correct 9 ms 16532 KB Output is correct
3 Incorrect 9 ms 16532 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 21848 KB Output is correct
2 Correct 45 ms 22236 KB Output is correct
3 Correct 46 ms 22240 KB Output is correct
4 Correct 40 ms 19148 KB Output is correct
5 Correct 36 ms 20808 KB Output is correct
6 Correct 38 ms 20212 KB Output is correct
7 Correct 37 ms 20440 KB Output is correct
8 Correct 36 ms 20784 KB Output is correct
9 Incorrect 37 ms 20536 KB Wrong Answer [7]
10 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16536 KB Output is correct
2 Correct 8 ms 16536 KB Output is correct
3 Correct 8 ms 16524 KB Output is correct
4 Correct 12 ms 17608 KB Output is correct
5 Correct 12 ms 17596 KB Output is correct
6 Correct 12 ms 17600 KB Output is correct
7 Correct 12 ms 17604 KB Output is correct
8 Correct 12 ms 17600 KB Output is correct
9 Incorrect 33 ms 22960 KB Wrong Answer [7]
10 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 21916 KB Output is correct
2 Incorrect 49 ms 22360 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 21964 KB Output is correct
2 Incorrect 48 ms 22256 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -