oj.uz

Submission #100999

# Submission time Handle Problem Language Result Execution time Memory
100999 2019-03-16T02:28:00 Z autumn_eel Amusement Park (JOI17_amusement_park) C++14
18 / 100
 70 ms 7788 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);
	}
	
	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){
      ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1800 KB Output is correct
2 Correct 5 ms 1904 KB Output is correct
3 Correct 6 ms 1796 KB Output is correct
4 Correct 6 ms 1908 KB Output is correct
5 Correct 6 ms 1792 KB Output is correct
6 Correct 5 ms 1792 KB Output is correct
7 Correct 7 ms 1884 KB Output is correct
8 Correct 8 ms 1932 KB Output is correct
9 Correct 6 ms 2052 KB Output is correct
10 Correct 5 ms 1664 KB Output is correct
11 Correct 10 ms 2216 KB Output is correct
12 Correct 5 ms 1664 KB Output is correct
13 Correct 7 ms 1932 KB Output is correct
14 Correct 6 ms 1924 KB Output is correct
15 Correct 7 ms 1924 KB Output is correct
16 Correct 7 ms 1884 KB Output is correct
17 Correct 7 ms 1804 KB Output is correct
18 Correct 7 ms 1804 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6136 KB Output is correct
2 Correct 60 ms 6232 KB Output is correct
3 Correct 64 ms 6192 KB Output is correct
4 Correct 41 ms 4712 KB Output is correct
5 Correct 39 ms 5184 KB Output is correct
6 Correct 36 ms 5184 KB Output is correct
7 Correct 36 ms 4928 KB Output is correct
8 Correct 36 ms 5184 KB Output is correct
9 Correct 43 ms 5240 KB Output is correct
10 Correct 34 ms 4808 KB Output is correct
11 Correct 36 ms 4936 KB Output is correct
12 Correct 34 ms 4400 KB Output is correct
13 Correct 35 ms 4520 KB Output is correct
14 Correct 38 ms 4764 KB Output is correct
15 Correct 37 ms 4808 KB Output is correct
16 Correct 40 ms 4844 KB Output is correct
17 Correct 34 ms 4808 KB Output is correct
18 Correct 43 ms 4816 KB Output is correct
19 Correct 36 ms 4808 KB Output is correct
20 Runtime error 37 ms 7788 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 5 ms 1664 KB Output is correct
3 Correct 6 ms 1800 KB Output is correct
4 Correct 8 ms 2332 KB Output is correct
5 Correct 11 ms 2468 KB Output is correct
6 Correct 9 ms 2340 KB Output is correct
7 Correct 9 ms 2344 KB Output is correct
8 Correct 8 ms 2332 KB Output is correct
9 Correct 27 ms 5652 KB Output is correct
10 Correct 27 ms 5712 KB Output is correct
11 Correct 24 ms 5696 KB Output is correct
12 Correct 5 ms 1792 KB Output is correct
13 Correct 6 ms 1920 KB Output is correct
14 Correct 6 ms 1664 KB Output is correct
15 Correct 6 ms 1696 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6084 KB Output is correct
2 Partially correct 66 ms 6084 KB Partially correct
3 Partially correct 64 ms 6132 KB Partially correct
4 Partially correct 40 ms 4664 KB Partially correct
5 Correct 40 ms 5504 KB Output is correct
6 Partially correct 46 ms 5176 KB Partially correct
7 Correct 51 ms 5176 KB Output is correct
8 Correct 40 ms 4940 KB Output is correct
9 Correct 37 ms 5048 KB Output is correct
10 Correct 34 ms 4940 KB Output is correct
11 Partially correct 36 ms 4800 KB Partially correct
12 Partially correct 32 ms 4528 KB Partially correct
13 Partially correct 34 ms 4400 KB Partially correct
14 Partially correct 28 ms 4756 KB Partially correct
15 Partially correct 44 ms 4848 KB Partially correct
16 Partially correct 46 ms 4840 KB Partially correct
17 Partially correct 41 ms 4772 KB Partially correct
18 Correct 45 ms 4588 KB Output is correct
19 Partially correct 49 ms 4808 KB Partially correct
20 Runtime error 30 ms 7752 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 57 ms 6400 KB Output is correct
2 Correct 70 ms 6368 KB Output is correct
3 Incorrect 64 ms 6092 KB Output isn't correct
4 Halted 0 ms 0 KB -