oj.uz

답안 #56968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56968 2018-07-13T11:19:56 Z hamzqq9 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 53 ms 12608 KB 
#include "Joi.h"

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define st first
#define nd second
#define pb push_back
#define MAX 20005
#define pw(x) (1LL<<(x))

static int N,M,CurBit,A[MAX],B[MAX],Bit[69],VAL[MAX];
static bool COME[MAX];
static vector<int> v[MAX];
static ll X;

static void CreateGraph() {

	for(int i=0;i<M;i++) {

		v[A[i]].pb(B[i]);
		v[B[i]].pb(A[i]);

	}

}

static void CreateBits() {

	for(int i=0;i<60;i++) {

		Bit[i]=((X&pw(i))>0);

	}

}

static void SpanningTree(int node,int ata) {

	if(CurBit==59 || COME[node]) return ;

	COME[node]=true;

	MessageBoard(node,Bit[++CurBit]);

	VAL[node]=1;

	for(int child:v[node]) {

		if(child==ata) continue ;

		SpanningTree(child,node);

	}

}

static void SUB2() {

	CreateGraph();
	CreateBits();

	CurBit=-1;

	SpanningTree(0,-1);

}

static void SUB3() {

}

static void SUB4() {

}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  	
	::N=N;
	::M=M;

	::X=X;

	for(int i=0;i<M;i++) {

		::A[i]=A[i];
		::B[i]=B[i];

	}

	for(int i=0;i<N;i++) VAL[i]=-1;

	if(T==1 || T==4) SUB4();

	if(T==2) SUB2();

	if(T==3) SUB3();

	for(int i=0;i<N;i++) {

		if(VAL[i]!=-1) continue ;

		MessageBoard(i,0);

	}

}

#include "Ioi.h"

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define st first
#define nd second
#define pb push_back
#define MAX 20005
#define pw(x) (1LL<<(x))

static int CurBit,M,N,P,V;
static int A[MAX],B[MAX];
static bool COME[MAX];
static vector<int> v[MAX],v2[MAX];
static ll X;

static void CreateGraph() {

	for(int i=0;i<M;i++) {

		v[A[i]].pb(B[i]);
		v[B[i]].pb(A[i]);

	}

}

static void SpanningTree(int node,int ata) {

	if(CurBit==59 || COME[node]) return ;

	COME[node]=true;

	++CurBit;

	if(~ata) {

		v2[ata].pb(node);

	}

	for(int child:v[node]) {

		if(child==ata) continue ;

		SpanningTree(child,node);

	}

}

static void dfs(int node,int ata) {

	++CurBit;

	X+=pw(CurBit)*V;

	for(int child:v2[node]) {

		V=Move(child);

		dfs(child,node);

		if(CurBit<59) V=Move(node);

	}

}

static int dist[MAX];
static bool vis[MAX];

static void findPath(int TO) {

	queue< pair<int,int> > Q;

	for(int i=0;i<N;i++) dist[i]=N+10,vis[i]=0;

	Q.push({TO,0});

	while(!Q.empty()) {

		pair<int,int> cur=Q.front();

		Q.pop();

		if(vis[cur.st]) continue ;

		vis[cur.st]=true;

		dist[cur.st]=cur.nd;

		for(int child:v[cur.st]) {

			Q.push({child,cur.nd+1});

		}

	}

	while(P!=TO) {

		for(int child:v[P]) {

			if(dist[child]==dist[P]-1) {

				V=Move(child);

				P=child;

				break ;

			}

		}

	}

}

static ll SUB2() {

	CreateGraph();

	CurBit=-1;

	SpanningTree(0,-1);

	findPath(0);

	CurBit=-1;

	dfs(P,-1);

	return X;

}

static ll SUB4() {

	return -1;

}

static ll SUB3() {

	return -1;

}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  
	::N=N;
	::M=M;
	::P=P;
	::V=V;

	for(int i=0;i<M;i++) {

		::A[i]=A[i];
		::B[i]=B[i];

	}

	if(T==1 || T==4) return SUB4();

	if(T==2) return SUB2();

	if(T==3) return SUB3();	

	assert(0); 

}

Subtask #1
0 / 8.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 5412 KB Output is correct
2 Correct 53 ms 6432 KB Output is correct
3 Correct 39 ms 6856 KB Output is correct
4 Correct 31 ms 6856 KB Output is correct
5 Correct 32 ms 6856 KB Output is correct
6 Correct 33 ms 6856 KB Output is correct
7 Correct 27 ms 6856 KB Output is correct
8 Correct 27 ms 6876 KB Output is correct
9 Correct 36 ms 6968 KB Output is correct
10 Correct 28 ms 7180 KB Output is correct
11 Correct 27 ms 7424 KB Output is correct
12 Correct 27 ms 7628 KB Output is correct
13 Correct 26 ms 7772 KB Output is correct
14 Correct 27 ms 7916 KB Output is correct
15 Correct 30 ms 8064 KB Output is correct
16 Correct 33 ms 8208 KB Output is correct
17 Correct 31 ms 8512 KB Output is correct
18 Correct 37 ms 8720 KB Output is correct
19 Correct 31 ms 8800 KB Output is correct
20 Correct 27 ms 9000 KB Output is correct
21 Correct 31 ms 9196 KB Output is correct
22 Correct 28 ms 9364 KB Output is correct
23 Correct 34 ms 9672 KB Output is correct
24 Correct 34 ms 9888 KB Output is correct
25 Correct 33 ms 9960 KB Output is correct
26 Correct 31 ms 10124 KB Output is correct
27 Correct 30 ms 10364 KB Output is correct
28 Correct 36 ms 10560 KB Output is correct
29 Correct 30 ms 10680 KB Output is correct
30 Correct 31 ms 10852 KB Output is correct
31 Correct 8 ms 10952 KB Output is correct
32 Correct 8 ms 10952 KB Output is correct
33 Correct 8 ms 10952 KB Output is correct
34 Correct 8 ms 10952 KB Output is correct
35 Correct 7 ms 10952 KB Output is correct
36 Correct 7 ms 10952 KB Output is correct
37 Correct 8 ms 10952 KB Output is correct
38 Correct 8 ms 10952 KB Output is correct
39 Correct 7 ms 10952 KB Output is correct
40 Correct 7 ms 10952 KB Output is correct
41 Correct 7 ms 10952 KB Output is correct
42 Correct 6 ms 10952 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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