oj.uz

답안 #66095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66095 2018-08-09T14:20:20 Z khohko Dungeon 2 (JOI16_dungeon2) C++17
0 / 100
 18 ms 4008 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[400];
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();
	if(k==2){mvb(); return 0;}
	n++;
	ll x=n;
	pr[x]=lst();
	if(f)v[x].pb({f,pr[x]});
	ll m=num();
	nm[x]=m;
	for(int i=1; i<=m; i++){
		if(i==g.top())continue;
		Move(i,2);
		ll k=go(x);
		if(k)v[x].pb({k,i});
	}
	mvb();
	return x;
}

ll f[400][400];
ll ef[700][700];
ll dp[400][400];
ll bk[400][400];
ll pw[400];
ll pas[400];
ll cr;

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

vector<ll> ord;
ll out[400];

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


void Inspect(int R) {
	go(0);

	for(int i=1; i<=n; i++){
		for(auto x:v[i]){
			ef[i][x.sc]=1;
			f[i][x.sc]=x.fr;
		}
	}

	pw[0]=1;
	for(int i=1; i<15; i++)pw[i]=pw[i-1]*3;
//	dfs(1);
	for(cr=0; cr<4; cr++)
		slv(1);
	//reverse(ord.begin(),ord.end());
	for(int i=1; i<=n; i++)
		for(int j=1; j<=nm[i]; j++){
			if(ef[i][j])continue;
			f[f[i][j]][bk[i][j]]=i;
		}

	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
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1016 KB Output is correct
2 Incorrect 4 ms 1076 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1076 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Runtime error 5 ms 1928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

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