oj.uz

Submission #125625

# Submission time Handle Problem Language Result Execution time Memory
125625 2019-07-06T05:40:01 Z Retro3014 Amusement Park (JOI17_amusement_park) C++17
10 / 100
 3000 ms 262148 KB 
#include "Joi.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 10000;
const int MAX_M = 20000;

vector<int> grpa[MAX_N+1];
vector<int> grp2[MAX_N+1];

int nmb[MAX_N+1];
int pa[MAX_N+1];

int chc[MAX_N+1];
int dgr[MAX_N+1];

set<int> s;

int find_leafa(int x){
	for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
		dgr[*it] = 0;
	}
	for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
		int k = (*it);
		if(k==0)	continue;
		if(chc[pa[k]]){
			dgr[pa[k]]++;
			dgr[k]++;
		}
	}
	for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
		int k = (*it);
		if(dgr[k]==1 && k!=x)	return k;
	}
}

void dfsa(int x){
	int t = -1;
	if(s.size()==60){
		int lf = find_leafa(pa[x]);
		t = lf;
		s.erase(lf);
		chc[lf] = false;
		nmb[x] = nmb[lf];
		chc[x] = true;
		s.insert(x);
	}else if(s.size()==59){
		s.insert(x);
		chc[x] = true;
		int cnt = 0;
		for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
			nmb[*it] = cnt;
			cnt++;
		}
	}else{
		s.insert(x);
		chc[x] = true;
	}
	for(int i=0; i<grpa[x].size(); i++){
		if(grpa[x][i]==pa[x])	continue;
		pa[grpa[x][i]] = x;
		dfsa(grpa[x][i]);
	}
	if(t!=-1){
		s.erase(x);
		s.insert(t);
		chc[t] = true;
		chc[x] = false;
	}
}


void Joi(int N, int M, int A[], int B[], long long X, int T) {
	for(int i=0; i<M; i++){
		grpa[A[i]].pb(B[i]); grpa[B[i]].pb(A[i]);
  	}
  	dfsa(0);
  	for(int i=0; i<N; i++){
  		ll t = ((ll)1<<nmb[i]);
  		MessageBoard(i, ((t & X)>0));
  		//cout<<i<<" "<<nmb[i]<<" "<<((t & X)>0)<<endl;
  		t*=2;
  	}
}

#include "Ioi.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 10000;
const int MAX_M = 20000;

vector<int> gp[MAX_N+1];
vector<int> gp2[MAX_N+1];

int num[MAX_N+1];
int p[MAX_N+1];

int chk[MAX_N+1];
int deg[MAX_N+1];

set<int> st;

int find_leaf(int x){
	for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
		deg[*it] = 0;
	}
	for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
		int k = (*it);
		if(k==0)	continue;
		if(chk[p[k]]){
			deg[p[k]]++;
			deg[k]++;
		}
	}
	for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
		int k = (*it);
		if(deg[k]==1 && k!=x)	return k;
	}
}

bool found = false;

int pos;

void dfs(int x){
	int t = -1;
	if(st.size()==60){
		int lf = find_leaf(p[x]);
		t = lf;
		st.erase(lf);
		chk[lf] = false;
		num[x] = num[lf];
		chk[x] = true;
		st.insert(x);
		if(x==pos){
			found = true;
			return;
		}
	}else if(st.size()==59){
		st.insert(x);
		chk[x] = true;
		int cnt = 0;
		for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
			num[*it] = cnt;
			cnt++;
		}
		if(st.find(pos)!=st.end()){
			found = true;
			return;
		}
	}else{
		st.insert(x);
		chk[x] = true;
	}
	for(int i=0; i<gp[x].size(); i++){
		if(gp[x][i]==p[x])	continue;
		p[gp[x][i]] = x;
		dfs(gp[x][i]);
		if(found)	return;
	}
	if(t!=-1){
		st.erase(x);
		st.insert(t);
		chk[t] = true;
		chk[x] = false;
	}
}


bool vst[MAX_N+1];
int ans[100];

void calc(int x){
	vst[x] = true;
	for(int i=0; i<gp[x].size(); i++){
		if(chk[gp[x][i]] && !vst[gp[x][i]]){
			int t = Move(gp[x][i]);
			ans[num[gp[x][i]]] = t;
			calc(gp[x][i]);
			Move(x);
		}
	}
}



long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	pos = P;
	for(int i=0; i<M; i++){
		gp[A[i]].pb(B[i]); gp[B[i]].pb(A[i]);
  	}
  	dfs(0);
  	ans[num[P]] = V;
  	calc(P);
  	ll answer=0;
  	ll t = 1;
  	for(int i=0; i<60; i++){
  		answer += (ll)ans[i] * t;
  		t*=2;
  	}
  	//cout<<answer<<endl;
  	return answer;
}

Compilation message

Joi.cpp: In function 'void dfsa(int)':
Joi.cpp:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<grpa[x].size(); i++){
               ~^~~~~~~~~~~~~~~
Joi.cpp: In function 'int find_leafa(int)':
Joi.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Ioi.cpp: In function 'void dfs(int)':
Ioi.cpp:91:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
Ioi.cpp: In function 'void calc(int)':
Ioi.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
Ioi.cpp: In function 'int find_leaf(int)':
Ioi.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1860 KB Output is correct
2 Correct 5 ms 1780 KB Output is correct
3 Correct 6 ms 1876 KB Output is correct
4 Correct 5 ms 2016 KB Output is correct
5 Correct 5 ms 1792 KB Output is correct
6 Correct 5 ms 1780 KB Output is correct
7 Correct 6 ms 1876 KB Output is correct
8 Correct 6 ms 1916 KB Output is correct
9 Correct 6 ms 1924 KB Output is correct
10 Execution timed out 3055 ms 155012 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1868 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1652 KB Output is correct
2 Correct 4 ms 1780 KB Output is correct
3 Correct 4 ms 1884 KB Output is correct
4 Correct 9 ms 2544 KB Output is correct
5 Correct 21 ms 2080 KB Output is correct
6 Correct 9 ms 2440 KB Output is correct
7 Correct 9 ms 2488 KB Output is correct
8 Correct 11 ms 2344 KB Output is correct
9 Correct 39 ms 5104 KB Output is correct
10 Correct 30 ms 5104 KB Output is correct
11 Correct 44 ms 5116 KB Output is correct
12 Correct 4 ms 2020 KB Output is correct
13 Correct 5 ms 1884 KB Output is correct
14 Correct 4 ms 1784 KB Output is correct
15 Correct 4 ms 1652 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 1952 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1972 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -