답안 #56970 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56970	2018-07-13T11:24:00 Z	hamzqq9	Amusement Park (JOI17_amusement_park)	C++14	20 / 100	50 ms	7440 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]=Bit[CurBit];

	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() {

	CreateBits();

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

		VAL[i]=Bit[i%60];

		MessageBoard(i,VAL[i]);

	}

}

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() {

	while(P%60 || P+59>=N) {

		P--;

		V=Move(P);

	}

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

		X+=pw(i-P)*V;

		if(i+1<N) V=Move(i+1);

	}

	return X;

}

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	7 ms	2016 KB	Wrong Answer [7]
2	Halted	0 ms	0 KB	-

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	5180 KB	Output is correct
2	Correct	50 ms	5952 KB	Output is correct
3	Correct	35 ms	5952 KB	Output is correct
4	Correct	22 ms	5952 KB	Output is correct
5	Correct	23 ms	5952 KB	Output is correct
6	Correct	25 ms	5952 KB	Output is correct
7	Correct	23 ms	5952 KB	Output is correct
8	Correct	23 ms	5952 KB	Output is correct
9	Correct	23 ms	5952 KB	Output is correct
10	Correct	27 ms	5952 KB	Output is correct
11	Correct	27 ms	5952 KB	Output is correct
12	Correct	23 ms	5952 KB	Output is correct
13	Correct	24 ms	5952 KB	Output is correct
14	Correct	18 ms	5952 KB	Output is correct
15	Correct	27 ms	5952 KB	Output is correct
16	Correct	27 ms	5952 KB	Output is correct
17	Correct	26 ms	5952 KB	Output is correct
18	Correct	19 ms	5952 KB	Output is correct
19	Correct	28 ms	5952 KB	Output is correct
20	Correct	30 ms	5952 KB	Output is correct
21	Correct	18 ms	5952 KB	Output is correct
22	Correct	19 ms	5952 KB	Output is correct
23	Correct	19 ms	5952 KB	Output is correct
24	Correct	20 ms	5952 KB	Output is correct
25	Correct	18 ms	5952 KB	Output is correct
26	Correct	23 ms	5952 KB	Output is correct
27	Correct	24 ms	5952 KB	Output is correct
28	Correct	25 ms	5952 KB	Output is correct
29	Correct	19 ms	5952 KB	Output is correct
30	Correct	27 ms	5952 KB	Output is correct
31	Correct	7 ms	5952 KB	Output is correct
32	Correct	7 ms	5952 KB	Output is correct
33	Correct	8 ms	5952 KB	Output is correct
34	Correct	7 ms	5952 KB	Output is correct
35	Correct	6 ms	5952 KB	Output is correct
36	Correct	7 ms	5952 KB	Output is correct
37	Correct	6 ms	5952 KB	Output is correct
38	Correct	7 ms	5952 KB	Output is correct
39	Correct	7 ms	5952 KB	Output is correct
40	Correct	6 ms	5952 KB	Output is correct
41	Correct	7 ms	5952 KB	Output is correct
42	Correct	6 ms	5952 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5952 KB	Output is correct
2	Correct	7 ms	5952 KB	Output is correct
3	Correct	6 ms	5952 KB	Output is correct
4	Correct	9 ms	5952 KB	Output is correct
5	Correct	8 ms	5952 KB	Output is correct
6	Correct	9 ms	5952 KB	Output is correct
7	Correct	10 ms	5952 KB	Output is correct
8	Correct	9 ms	5952 KB	Output is correct
9	Correct	19 ms	5952 KB	Output is correct
10	Correct	17 ms	5952 KB	Output is correct
11	Correct	17 ms	5952 KB	Output is correct
12	Correct	8 ms	5952 KB	Output is correct
13	Correct	7 ms	5952 KB	Output is correct
14	Correct	7 ms	5952 KB	Output is correct
15	Correct	7 ms	5952 KB	Output is correct

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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

답안 #56970

Compilation message

Subtask #1 0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 55.0

Subtask #5 0 / 17.0

Subtask #1
0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 55.0

Subtask #5
0 / 17.0