oj.uz

Submission #101002

# Submission time Handle Problem Language Result Execution time Memory
101002 2019-03-16T02:46:52 Z autumn_eel Amusement Park (JOI17_amusement_park) C++14
18 / 100
 70 ms 7984 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;
			}
		}
		assert(Min<=900);
		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);
	}
	
	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 5 ms 1928 KB Output is correct
2 Correct 7 ms 2040 KB Output is correct
3 Correct 7 ms 1804 KB Output is correct
4 Correct 6 ms 2040 KB Output is correct
5 Correct 6 ms 1800 KB Output is correct
6 Correct 5 ms 2036 KB Output is correct
7 Correct 6 ms 1804 KB Output is correct
8 Correct 6 ms 2024 KB Output is correct
9 Correct 8 ms 1804 KB Output is correct
10 Correct 7 ms 1908 KB Output is correct
11 Correct 11 ms 2184 KB Output is correct
12 Correct 7 ms 1924 KB Output is correct
13 Correct 6 ms 1924 KB Output is correct
14 Correct 6 ms 1804 KB Output is correct
15 Correct 7 ms 2052 KB Output is correct
16 Correct 8 ms 1888 KB Output is correct
17 Correct 6 ms 1932 KB Output is correct
18 Correct 6 ms 1892 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6408 KB Output is correct
2 Correct 70 ms 6336 KB Output is correct
3 Correct 66 ms 6228 KB Output is correct
4 Correct 48 ms 4816 KB Output is correct
5 Correct 48 ms 5444 KB Output is correct
6 Correct 44 ms 5320 KB Output is correct
7 Correct 46 ms 5304 KB Output is correct
8 Correct 43 ms 5256 KB Output is correct
9 Correct 46 ms 5424 KB Output is correct
10 Correct 50 ms 5048 KB Output is correct
11 Correct 41 ms 5080 KB Output is correct
12 Correct 37 ms 4776 KB Output is correct
13 Correct 52 ms 4512 KB Output is correct
14 Correct 43 ms 4892 KB Output is correct
15 Correct 39 ms 4876 KB Output is correct
16 Correct 59 ms 4920 KB Output is correct
17 Correct 39 ms 4928 KB Output is correct
18 Correct 38 ms 4804 KB Output is correct
19 Correct 38 ms 4824 KB Output is correct
20 Runtime error 37 ms 7904 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 1664 KB Output is correct
2 Correct 6 ms 1792 KB Output is correct
3 Correct 6 ms 1664 KB Output is correct
4 Correct 12 ms 2344 KB Output is correct
5 Correct 10 ms 2468 KB Output is correct
6 Correct 8 ms 2332 KB Output is correct
7 Correct 9 ms 2392 KB Output is correct
8 Correct 11 ms 2332 KB Output is correct
9 Correct 31 ms 5696 KB Output is correct
10 Correct 32 ms 5832 KB Output is correct
11 Correct 35 ms 5836 KB Output is correct
12 Correct 6 ms 1664 KB Output is correct
13 Correct 8 ms 1920 KB Output is correct
14 Correct 6 ms 1800 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 65 ms 6320 KB Output is correct
2 Partially correct 59 ms 6364 KB Partially correct
3 Partially correct 61 ms 6228 KB Partially correct
4 Partially correct 44 ms 4984 KB Partially correct
5 Correct 57 ms 5652 KB Output is correct
6 Partially correct 53 ms 5440 KB Partially correct
7 Correct 54 ms 5248 KB Output is correct
8 Correct 44 ms 5048 KB Output is correct
9 Correct 46 ms 5040 KB Output is correct
10 Correct 33 ms 5212 KB Output is correct
11 Partially correct 37 ms 4800 KB Partially correct
12 Partially correct 36 ms 4592 KB Partially correct
13 Partially correct 38 ms 4520 KB Partially correct
14 Partially correct 46 ms 4700 KB Partially correct
15 Partially correct 41 ms 4784 KB Partially correct
16 Partially correct 37 ms 5068 KB Partially correct
17 Partially correct 36 ms 4928 KB Partially correct
18 Correct 37 ms 4920 KB Output is correct
19 Partially correct 41 ms 4920 KB Partially correct
20 Runtime error 36 ms 7984 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 55 ms 6172 KB Output is correct
2 Correct 53 ms 6212 KB Output is correct
3 Incorrect 51 ms 6356 KB Output isn't correct
4 Halted 0 ms 0 KB -