oj.uz

Submission #100998

# Submission time Handle Problem Language Result Execution time Memory
100998 2019-03-16T02:20:53 Z autumn_eel Amusement Park (JOI17_amusement_park) C++14
18 / 100
 64 ms 7780 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);
	}
	
	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;
     ~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1792 KB Output is correct
2 Correct 5 ms 1792 KB Output is correct
3 Correct 7 ms 1796 KB Output is correct
4 Correct 6 ms 1800 KB Output is correct
5 Correct 6 ms 1800 KB Output is correct
6 Correct 6 ms 1664 KB Output is correct
7 Correct 7 ms 2040 KB Output is correct
8 Correct 7 ms 2048 KB Output is correct
9 Correct 8 ms 1832 KB Output is correct
10 Correct 7 ms 1900 KB Output is correct
11 Correct 10 ms 2232 KB Output is correct
12 Correct 6 ms 1792 KB Output is correct
13 Correct 6 ms 1668 KB Output is correct
14 Correct 6 ms 1932 KB Output is correct
15 Correct 5 ms 1924 KB Output is correct
16 Correct 7 ms 1804 KB Output is correct
17 Correct 6 ms 1796 KB Output is correct
18 Correct 7 ms 1924 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5956 KB Output is correct
2 Correct 60 ms 6056 KB Output is correct
3 Correct 54 ms 6108 KB Output is correct
4 Correct 40 ms 4812 KB Output is correct
5 Correct 47 ms 5276 KB Output is correct
6 Correct 45 ms 5192 KB Output is correct
7 Correct 38 ms 5192 KB Output is correct
8 Correct 51 ms 5040 KB Output is correct
9 Correct 39 ms 5312 KB Output is correct
10 Correct 40 ms 4672 KB Output is correct
11 Correct 46 ms 4800 KB Output is correct
12 Correct 32 ms 4400 KB Output is correct
13 Correct 37 ms 4536 KB Output is correct
14 Correct 40 ms 4792 KB Output is correct
15 Correct 64 ms 4920 KB Output is correct
16 Correct 40 ms 4900 KB Output is correct
17 Correct 41 ms 4784 KB Output is correct
18 Correct 43 ms 4800 KB Output is correct
19 Correct 40 ms 4792 KB Output is correct
20 Runtime error 32 ms 7608 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 1828 KB Output is correct
3 Correct 7 ms 1912 KB Output is correct
4 Correct 7 ms 2468 KB Output is correct
5 Correct 10 ms 2444 KB Output is correct
6 Correct 11 ms 2332 KB Output is correct
7 Correct 8 ms 2348 KB Output is correct
8 Correct 11 ms 2468 KB Output is correct
9 Correct 34 ms 5824 KB Output is correct
10 Correct 35 ms 5676 KB Output is correct
11 Correct 30 ms 5708 KB Output is correct
12 Correct 5 ms 1700 KB Output is correct
13 Correct 6 ms 1928 KB Output is correct
14 Correct 6 ms 1796 KB Output is correct
15 Correct 4 ms 1592 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6060 KB Output is correct
2 Partially correct 59 ms 6072 KB Partially correct
3 Partially correct 62 ms 6236 KB Partially correct
4 Partially correct 39 ms 4792 KB Partially correct
5 Correct 45 ms 5488 KB Output is correct
6 Partially correct 40 ms 5184 KB Partially correct
7 Correct 41 ms 5184 KB Output is correct
8 Correct 40 ms 4928 KB Output is correct
9 Correct 37 ms 5076 KB Output is correct
10 Correct 44 ms 4928 KB Output is correct
11 Partially correct 45 ms 4792 KB Partially correct
12 Partially correct 33 ms 4528 KB Partially correct
13 Partially correct 31 ms 4556 KB Partially correct
14 Partially correct 43 ms 4784 KB Partially correct
15 Partially correct 39 ms 4656 KB Partially correct
16 Partially correct 38 ms 4800 KB Partially correct
17 Partially correct 39 ms 4924 KB Partially correct
18 Correct 41 ms 4784 KB Output is correct
19 Partially correct 48 ms 4672 KB Partially correct
20 Runtime error 35 ms 7780 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 58 ms 5980 KB Output is correct
2 Correct 56 ms 5960 KB Output is correct
3 Incorrect 50 ms 6132 KB Output isn't correct
4 Halted 0 ms 0 KB -