oj.uz

답안 #66076

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66076 2018-08-09T13:36:37 Z khohko Dungeon 2 (JOI16_dungeon2) C++17
44 / 100
 67 ms 49192 KB 
#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define ARRS ((ll)(2e6+100))
#define MAX ((ll)(1e9+100))
#define MOD ((ll)(1e9+7))

//void Inspect(int R);
//void Answer(int D, int A);
//void Move(int I, int V);
//int NumberOfRoads();
//int LastRoad();
//int Color();
#define num NumberOfRoads
#define lst LastRoad
#define clr Color

stack<ll> g;
vector<pair<ll,ll> > v[ARRS];
ll C=1;
ll pr[400];
ll nm[400];
void mvb(){
	ll t=g.top();
	g.pop();
	if(t>=0)Move(t,2);
}

ll n=0;

ll go(ll f){
	g.push(LastRoad());
	ll k=Color();
	//cout<<k<<" = "<<lst()<<endl;
	if(k==2){mvb(); return 0;}
	n++;
	ll x=n;
	pr[x]=lst();
	if(f)v[x].pb({f,lst()});
	ll m=num();
	nm[x]=m;
	for(int i=1; i<=m; i++){
		if(i==g.top())continue;
		//cout<<x<<" -> "<<i<<endl;
		Move(i,2);
		ll k=go(x);
		if(k)v[x].pb({k,i});
			//v[k].pb(x);
		//}
	}
	mvb();
	return x;
}

ll f[400][400];
ll dp[400][400];
ll pw[400];
ll pas[400];
ll cr;

ll gc(ll x){
	return (x/pw[cr])%3+1;
}

void dfs(ll x){
	for(auto y:v[x]){
		if(y.sc==pr[x])continue;
		Move(y.sc,gc(x));
		dfs(y.fr);
	}
	if(pr[x]>=0)
	Move(pr[x],gc(x));
}

void slv(ll x){
	for(auto y:v[x]){
		if(y.sc==pr[x])continue;
		Move(y.sc,clr());
		slv(y.fr);
	}
	for(int i=1; i<=num(); i++){
		Move(i,clr());
		f[x][i]+=(clr()-1)*pw[cr];
		Move(lst(),clr());
	}
	if(pr[x]>=0)
	Move(pr[x],clr());
}


void Inspect(int R) {
	go(0);
	pw[0]=1;
	for(int i=1; i<15; i++)pw[i]=pw[i-1]*3;
	for(cr=0; cr<8; cr++){
		dfs(1);
		slv(1);
	}

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			dp[i][j]=MAX;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=nm[i]; j++)
			dp[i][f[i][j]]=1;

	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);

	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)
			pas[dp[i][j]]++;

	for(int i = 1; i <= R; i++)
		Answer(i, pas[i]);
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 47736 KB Output is correct
2 Correct 45 ms 47844 KB Output is correct
3 Correct 50 ms 47948 KB Output is correct
4 Correct 47 ms 47948 KB Output is correct
5 Correct 45 ms 47948 KB Output is correct
6 Correct 53 ms 47948 KB Output is correct
7 Correct 52 ms 47948 KB Output is correct
8 Correct 51 ms 47948 KB Output is correct
9 Correct 53 ms 47976 KB Output is correct
10 Correct 47 ms 47976 KB Output is correct
11 Correct 45 ms 48104 KB Output is correct
12 Correct 50 ms 48104 KB Output is correct
13 Correct 48 ms 48104 KB Output is correct
14 Correct 51 ms 48104 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 48104 KB Output is correct
2 Correct 42 ms 48104 KB Output is correct
3 Correct 50 ms 48104 KB Output is correct
4 Correct 47 ms 48104 KB Output is correct
5 Correct 45 ms 48104 KB Output is correct
6 Correct 44 ms 48104 KB Output is correct
7 Correct 43 ms 48104 KB Output is correct
8 Correct 48 ms 48104 KB Output is correct
9 Correct 44 ms 48104 KB Output is correct
10 Correct 44 ms 48104 KB Output is correct
11 Correct 51 ms 48104 KB Output is correct
12 Correct 45 ms 48104 KB Output is correct
13 Correct 51 ms 48104 KB Output is correct
14 Correct 44 ms 48104 KB Output is correct
15 Correct 45 ms 48104 KB Output is correct

Subtask #3
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 49192 KB Output isn't correct
2 Halted 0 ms 0 KB -