oj.uz

Submission #101000

# Submission time Handle Problem Language Result Execution time Memory
101000 2019-03-16T02:45:30 Z autumn_eel Amusement Park (JOI17_amusement_park) C++14
18 / 100
 66 ms 8000 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

#include "Joi.h"

vector<int>E[20000];
vector<int>vs;
bool used[20000];

void dfs(int v,int p){
	used[v]=true;
	vs.push_back(v);
	for(int u:E[v]){
		if(used[u])continue;
		dfs(u,v);
		vs.push_back(v);
	}
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	rep(i,M){
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	dfs(0,-1);
	set<int>se1,se2;
	for(int v:vs){
		if(!se1.count(v)){
			se2.insert(v);
		}
		if(se2.size()==60){
			int cnt=0;
			for(int i:se2){
				MessageBoard(i,X>>cnt&1);
				cnt++;
			}
			for(int i:se2){
				se1.insert(i);
			}
			se2.clear();
		}
	}
	int cnt=0;
	for(int i:se2){
		MessageBoard(i,X>>cnt&1);
		cnt++;
	}
}

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

#include "Ioi.h"

static vector<int>E[20000];
static vector<int>vs;
static int vid[20000];
static bool used[20000];

static void dfs(int v,int p){
	used[v]=true;
	vid[v]=vs.size();
	vs.push_back(v);
	for(int u:E[v]){
		if(used[u])continue;
		dfs(u,v);
		vs.push_back(v);
	}
}

long long Ioi(int N, int M, int A[], int B[], int Pos, int V, int T) {
	rep(i,M){
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	dfs(0,-1);
	set<int>se1,se2;
	map<int,int>id;
	for(int v:vs){
		if(!se1.count(v)){
			se2.insert(v);
		}
		if(se2.size()==60){
			int cnt=0;
			for(int i:se2){
				id[i]=cnt;
				cnt++;
			}
			for(int i:se2){
				se1.insert(i);
			}
			se2.clear();
		}
	}
	int cnt=0;
	for(int i:se2){
		id[i]=cnt;
		cnt++;
	}
	int x=vid[Pos];
	
	set<int>se;
	int r;
	for(r=x;r<vs.size();r++){
		se.insert(id[vs[r]]);
		if(se.size()==60)break;
	}
	if(r==vs.size())r=vs.size()-1;
	int l;
	for(l=x;l>=0;l--){
		se.insert(id[vs[l]]);
		if(se.size()==60)break;
	}
	if(l==-1)l=0;
	
	set<int>Se;
	int l2;
	for(l2=x;l2>=0;l2--){
		Se.insert(id[vs[l2]]);
		if(Se.size()==60)break;
	}
	if(l2==-1)l2=0;
	int r2;
	for(r2=x;r2<vs.size();r2++){
		Se.insert(id[vs[r2]]);
		if(Se.size()==60)break;
	}
	if(r2==vs.size())r2=vs.size()-1;
	if(r2-l2+min(r2-x,x-l2)<r-l+min(r-x,x-l)){
		swap(l,l2);
		swap(r,r2);
	}
	
	set<int>SE;
	int l3=x,r3=x;
	while(1){
		if(l3>0){
			SE.insert(id[vs[--l3]]);
		}
		if(r3<vs.size()-1){
			SE.insert(id[vs[++r3]]);
		}
		if(SE.size()==60)break;
	}
	
	if(r3-l3+min(r3-x,x-l3)<r-l+min(r-x,x-l)){
		swap(l,l3);
		swap(r,r3);
	}
	
	map<int,vector<int>>MP;
	rep(i,vs.size()){
		MP[id[vs[i]]].push_back(i);
	}
	int l4=x,r4=x;
	rep(i,60){
		int Min=INT_MAX;
		int t=-1;
		auto it=lower_bound(MP[i].begin(),MP[i].end(),x);
		if(it!=MP[i].end()){
			Min=*it-x;
			t=*it;
		}
		if(it!=MP[i].begin()){
			it--;
			if(Min>x-*it){
				Min=x-*it;
				t=*it;
			}
		}
		l4=min(l4,*it);
		r4=max(r4,*it);
	}
	if(r4-l4+min(r4-x,x-l4)<r-l+min(r-x,x-l)){
		swap(l,l4);
		swap(r,r4);
	}
		
	assert(r-l+min(r-x,x-l)<=900);
	
	ll ans=0;
	ans|=ll(V)<<id[Pos];
	if(abs(x-l)<abs(x-r)){
		//left
		for(int i=x-1;i>=l;i--){
			ans|=ll(Move(vs[i]))<<id[vs[i]];
		}
		for(int i=l+1;i<=r;i++){
			ans|=ll(Move(vs[i]))<<id[vs[i]];
		}
	}
	else{
		//right
		for(int i=x+1;i<=r;i++){
			ans|=ll(Move(vs[i]))<<id[vs[i]];
		}
		for(int i=r-1;i>=l;i--){
			ans|=ll(Move(vs[i]))<<id[vs[i]];
		}
	}
	return ans;
	
}

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:58:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(r=x;r<vs.size();r++){
          ~^~~~~~~~~~
Ioi.cpp:62:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(r==vs.size())r=vs.size()-1;
     ~^~~~~~~~~~~
Ioi.cpp:78:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(r2=x;r2<vs.size();r2++){
           ~~^~~~~~~~~~
Ioi.cpp:82:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(r2==vs.size())r2=vs.size()-1;
     ~~^~~~~~~~~~~
Ioi.cpp:94:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r3<vs.size()-1){
      ~~^~~~~~~~~~~~
Ioi.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
Ioi.cpp:106:2: note: in expansion of macro 'rep'
  rep(i,vs.size()){
  ^~~
Ioi.cpp:112:7: warning: variable 't' set but not used [-Wunused-but-set-variable]
   int t=-1;
       ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1916 KB Output is correct
2 Correct 6 ms 1800 KB Output is correct
3 Correct 6 ms 1884 KB Output is correct
4 Correct 6 ms 1800 KB Output is correct
5 Correct 4 ms 1664 KB Output is correct
6 Correct 5 ms 1928 KB Output is correct
7 Correct 6 ms 1804 KB Output is correct
8 Correct 6 ms 1896 KB Output is correct
9 Correct 7 ms 1968 KB Output is correct
10 Correct 5 ms 1820 KB Output is correct
11 Correct 8 ms 2224 KB Output is correct
12 Correct 6 ms 1664 KB Output is correct
13 Correct 7 ms 1884 KB Output is correct
14 Correct 6 ms 1804 KB Output is correct
15 Correct 7 ms 1804 KB Output is correct
16 Correct 6 ms 1884 KB Output is correct
17 Correct 7 ms 2016 KB Output is correct
18 Correct 6 ms 1932 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 6212 KB Output is correct
2 Correct 66 ms 6324 KB Output is correct
3 Correct 62 ms 6320 KB Output is correct
4 Correct 52 ms 5056 KB Output is correct
5 Correct 44 ms 5448 KB Output is correct
6 Correct 41 ms 5192 KB Output is correct
7 Correct 44 ms 5172 KB Output is correct
8 Correct 50 ms 5320 KB Output is correct
9 Correct 60 ms 5324 KB Output is correct
10 Correct 45 ms 4952 KB Output is correct
11 Correct 44 ms 5056 KB Output is correct
12 Correct 43 ms 4888 KB Output is correct
13 Correct 37 ms 4656 KB Output is correct
14 Correct 45 ms 4804 KB Output is correct
15 Correct 45 ms 4972 KB Output is correct
16 Correct 40 ms 4912 KB Output is correct
17 Correct 42 ms 5080 KB Output is correct
18 Correct 43 ms 4928 KB Output is correct
19 Correct 43 ms 4808 KB Output is correct
20 Runtime error 33 ms 8000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1928 KB Output is correct
2 Correct 7 ms 1816 KB Output is correct
3 Correct 6 ms 1800 KB Output is correct
4 Correct 10 ms 2448 KB Output is correct
5 Correct 9 ms 2476 KB Output is correct
6 Correct 9 ms 2468 KB Output is correct
7 Correct 8 ms 2432 KB Output is correct
8 Correct 8 ms 2204 KB Output is correct
9 Correct 25 ms 5696 KB Output is correct
10 Correct 31 ms 5832 KB Output is correct
11 Correct 29 ms 5824 KB Output is correct
12 Correct 6 ms 1664 KB Output is correct
13 Correct 5 ms 1800 KB Output is correct
14 Correct 5 ms 1928 KB Output is correct
15 Correct 4 ms 1664 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6228 KB Output is correct
2 Partially correct 53 ms 6340 KB Partially correct
3 Partially correct 53 ms 6240 KB Partially correct
4 Partially correct 45 ms 5060 KB Partially correct
5 Correct 46 ms 5624 KB Output is correct
6 Partially correct 44 ms 5448 KB Partially correct
7 Correct 45 ms 5320 KB Output is correct
8 Correct 45 ms 5212 KB Output is correct
9 Correct 49 ms 5216 KB Output is correct
10 Correct 40 ms 4996 KB Output is correct
11 Partially correct 37 ms 5156 KB Partially correct
12 Partially correct 37 ms 4648 KB Partially correct
13 Partially correct 40 ms 4784 KB Partially correct
14 Partially correct 41 ms 4920 KB Partially correct
15 Partially correct 46 ms 4944 KB Partially correct
16 Partially correct 40 ms 4928 KB Partially correct
17 Partially correct 45 ms 4936 KB Partially correct
18 Correct 51 ms 4792 KB Output is correct
19 Partially correct 53 ms 4792 KB Partially correct
20 Runtime error 35 ms 7876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6220 KB Output is correct
2 Correct 51 ms 6372 KB Output is correct
3 Incorrect 52 ms 6228 KB Output isn't correct
4 Halted 0 ms 0 KB -