Submission #716593

#	Time	Username	Problem	Language	Result	Execution time	Memory
716593		dum123	Amusement Park (JOI17_amusement_park)	C++14	0 / 100	64 ms	9444 KiB

Joi

#include "Joi.h"

# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;

vector<int> edge1[10001];
int bt1[10001], t1;
bool vis1[10001], ck1[10001];
vector<int> nt1;
vector<int> sp1[10001];
int lf;

void dfs1(int a, int pr) {
	if(lf >= 0) return;
	int ct = 0, v = -1;
	for(int k=0;k<edge1[a].size();k++) {
		if(!ck1[edge1[a][k]] || !vis1[edge1[a][k]]) continue;
		if(edge1[a][k] != pr) dfs1(edge1[a][k], a);
		ct++;
		v = edge1[a][k];
	}
	if(pr != -1 && ct == 1 && v == pr) lf = a;
}

bool jk(int a) {
	for(int i=0;i<edge1[a].size();i++) if(!vis1[edge1[a][i]]) return 0;
	return 1;
}

void dfs(int a, int pr) {
	vis1[a] = 1;
	if(t1 == 60) {
		lf = -1;
		for(auto p : sp1[pr]) ck1[p] = 1;
		
		dfs1(pr, -1);
		
		for(auto p : sp1[pr]) ck1[p] = 0;
		for(auto p : sp1[pr]) {
			if(p != lf) sp1[a].push_back(p);
		}
		if(jk(pr)) sp1[pr].clear();
		
		sp1[a].push_back(a);
		bt1[a] = bt1[lf];
		for(int k=0;k<edge1[a].size();k++) {
			if(!vis1[edge1[a][k]]) dfs(edge1[a][k], a);
		}
	} else {
		
		bt1[a] = t1++;
		nt1.push_back(a);
		if(t1 == 60) {
			for(auto p : nt1) {
				if(!jk(p)) sp1[p] = nt1;
			}
		}
		
		ck1[a] = 1;
		for(int k=0;k<edge1[a].size();k++) {
			if(!vis1[edge1[a][k]]) dfs(edge1[a][k], a);
		}
	}
}

int par2[10009];
int findParent2(int x){
	if(par2[x]==x) return x;
	return par2[x] = findParent2(par2[x]);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	
		t1 = 0;
	for(int k=0;k<N;k++) {
		edge1[k].clear();
		par2[k]= k;
		bt1[k] = -1;
		ck1[k] = 0;
		vis1[k] = 0;
	}
	for(int i=0;i<M;i++) {
		if(findParent2(A[i]) != findParent2(B[i])){
		edge1[A[i]].push_back(B[i]);
		edge1[B[i]].push_back(A[i]);
		par2[findParent2(A[i])] = findParent2(B[i]);
		}
		
	}
	dfs(0, -1);
	for(int i=0;i<N;i++) {
	//	cout<<i<<" "<<bt[i]<<" "<<(X&(1 << bt[i]))<<endl;
		if(X&(1ll << bt1[i])) MessageBoard(i, 1);
		else MessageBoard(i, 0);
	}

}

Ioi

#include "Ioi.h"
# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;

vector<int> edge[10001];
int bt[10001], t;
bool viss[10001], ck[10001];
vector<int> nt;
vector<int> sp[10001];
int lf1;

bool jk1(int a) {
	for(int i=0;i<edge[a].size();i++) if(!viss[edge[a][i]]) return 0;
	return 1;
}


void dfs12(int a, int pr) {
	if(lf1 >= 0) return;
	int ct = 0, v = -1;
	for(int k=0;k<edge[a].size();k++) {
		if(!ck[edge[a][k]] || ! viss[edge[a][k]]) continue;
		if(edge[a][k] != pr) dfs12(edge[a][k], a);
		ct++;
		v = edge[a][k];
	}
	if(pr != -1 && ct == 1 && v == pr) lf1 = a;
}

void dfs2(int a, int pr) {
	viss[a] = 1;
	if(t == 60) {
		lf1 = -1;
		for(auto p : sp[pr]) ck[p] = 1;
		dfs12(pr, -1);
		for(auto p : sp[pr]) ck[p] = 0;
		for(auto p : sp[pr]) {
			if(p != lf1) sp[a].push_back(p);
		}
		sp[a].push_back(a);
		if(jk1(pr)) sp[pr].clear();
		
		bt[a] = bt[lf1];
		for(int k=0;k<edge[a].size();k++) {
			if(!viss[edge[a][k]]) dfs2(edge[a][k], a);
		}
		ck[a] = 0;
		ck[lf1] = 1;
	} else {
		bt[a] = t++;
		nt.push_back(a);
		if(t == 60) {
			for(auto p : nt) {
				if(!jk1(p)) sp[p] = nt;	
			}
		}
		
		ck[a] = 1;
		for(int k=0;k<edge[a].size();k++) {
			if(!viss[edge[a][k]]) dfs2(edge[a][k], a);
		}
	}
}

int fnd[101], vis[100001];
int ctt = 60, x = 0;

void dfss(int a, int bf) {
	for(int k=0;k<edge[a].size();k++) {
		if(fnd[bt[edge[a][k]]] == -1) {
			fnd[bt[edge[a][k]]] = move(edge[a][k]);
			dfss(edge[a][k], a);
		}
	}
	if(bf != -1) fnd[bt[bf]] = move(bf);
}

int par[10009];
int findParent(int x){
	if(par[x]==x) return x;
	return par[x] = findParent(par[x]);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  	t = 0;
	for(int k=0;k<N;k++) {
		edge[k].clear();
		par[k] = k;
		bt[k] = -1;
		viss[k] = 0;
		ck[k] = 0;
	}
	for(int i=0;i<M;i++) {
		if(findParent(A[i]) != findParent(B[i])){
		edge[A[i]].push_back(B[i]);
		edge[B[i]].push_back(A[i]);
		par[findParent(A[i])] = findParent(B[i]);
		}
		
	}
	dfs2(0, -1);
	
	for(int i=0;i<60;i++) fnd[i] = -1;
	fnd[bt[P]] = V;
	dfss(P, -1);
	ll ans = 0ll;
	for(ll i=0;i<60;i++) {
	//	cout<<i<<" "<<fnd[i]<<endl;
		if(fnd[i] == 1) ans += (1ll << i);
	}
	return ans;
}

Compilation message (stderr)

Joi.cpp: In function 'void dfs1(int, int)':
Joi.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int k=0;k<edge1[a].size();k++) {
      |              ~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'bool jk(int)':
Joi.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i=0;i<edge1[a].size();i++) if(!vis1[edge1[a][i]]) return 0;
      |              ~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int k=0;k<edge1[a].size();k++) {
      |               ~^~~~~~~~~~~~~~~~
Joi.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int k=0;k<edge1[a].size();k++) {
      |               ~^~~~~~~~~~~~~~~~

Ioi.cpp: In function 'bool jk1(int)':
Ioi.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i=0;i<edge[a].size();i++) if(!viss[edge[a][i]]) return 0;
      |              ~^~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs12(int, int)':
Ioi.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int k=0;k<edge[a].size();k++) {
      |              ~^~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs2(int, int)':
Ioi.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int k=0;k<edge[a].size();k++) {
      |               ~^~~~~~~~~~~~~~~
Ioi.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int k=0;k<edge[a].size();k++) {
      |               ~^~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfss(int, int)':
Ioi.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int k=0;k<edge[a].size();k++) {
      |              ~^~~~~~~~~~~~~~~

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