oj.uz

답안 #100993

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100993 2019-03-16T01:41:33 Z autumn_eel Amusement Park (JOI17_amusement_park) C++14
10 / 100
 373 ms 263168 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;
int vid[20000];

void dfs(int v,int p){
	vid[v]=vs.size();
	vs.push_back(v);
	for(int u:E[v]){
		if(u==p)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 void dfs(int v,int p){
	vid[v]=vs.size();
	vs.push_back(v);
	for(int u:E[v]){
		if(u==p)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:55:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(r=x;r<vs.size();r++){
          ~^~~~~~~~~~
Ioi.cpp:59: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 4 ms 1664 KB Output is correct
2 Correct 6 ms 1800 KB Output is correct
3 Correct 6 ms 1668 KB Output is correct
4 Correct 6 ms 1664 KB Output is correct
5 Correct 6 ms 1664 KB Output is correct
6 Correct 6 ms 1664 KB Output is correct
7 Correct 6 ms 1844 KB Output is correct
8 Correct 6 ms 1796 KB Output is correct
9 Correct 6 ms 1932 KB Output is correct
10 Correct 5 ms 1792 KB Output is correct
11 Runtime error 265 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 370 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1664 KB Output is correct
2 Correct 5 ms 1664 KB Output is correct
3 Correct 6 ms 1692 KB Output is correct
4 Correct 8 ms 2204 KB Output is correct
5 Correct 8 ms 2448 KB Output is correct
6 Correct 10 ms 2352 KB Output is correct
7 Correct 8 ms 2448 KB Output is correct
8 Correct 8 ms 2468 KB Output is correct
9 Correct 32 ms 5768 KB Output is correct
10 Correct 28 ms 5876 KB Output is correct
11 Correct 26 ms 5880 KB Output is correct
12 Correct 6 ms 1792 KB Output is correct
13 Correct 6 ms 1796 KB Output is correct
14 Correct 6 ms 1796 KB Output is correct
15 Correct 6 ms 1664 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 373 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 317 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -