oj.uz

답안 #100994

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100994 2019-03-16T01:44:47 Z autumn_eel Amusement Park (JOI17_amusement_park) C++14
10 / 100
 35 ms 5704 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,N-1){
		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,N-1){
		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;
	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:57:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(r=x;r<vs.size();r++){
          ~^~~~~~~~~~
Ioi.cpp:61:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(r==vs.size())r=vs.size()-1;
     ~^~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1664 KB Output is correct
2 Correct 6 ms 1800 KB Output is correct
3 Correct 6 ms 1924 KB Output is correct
4 Correct 5 ms 1664 KB Output is correct
5 Correct 6 ms 1688 KB Output is correct
6 Correct 5 ms 1664 KB Output is correct
7 Correct 6 ms 1924 KB Output is correct
8 Correct 7 ms 1892 KB Output is correct
9 Correct 8 ms 1924 KB Output is correct
10 Correct 7 ms 1912 KB Output is correct
11 Incorrect 8 ms 2048 KB Wrong Answer [4]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 4352 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1800 KB Output is correct
2 Correct 5 ms 1664 KB Output is correct
3 Correct 5 ms 1792 KB Output is correct
4 Correct 10 ms 2352 KB Output is correct
5 Correct 9 ms 2332 KB Output is correct
6 Correct 9 ms 2572 KB Output is correct
7 Correct 12 ms 2340 KB Output is correct
8 Correct 10 ms 2360 KB Output is correct
9 Correct 25 ms 5696 KB Output is correct
10 Correct 35 ms 5704 KB Output is correct
11 Correct 22 ms 5704 KB Output is correct
12 Correct 5 ms 1696 KB Output is correct
13 Correct 5 ms 1800 KB Output is correct
14 Correct 6 ms 1928 KB Output is correct
15 Correct 6 ms 1924 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 4352 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 4376 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -