oj.uz

답안 #66072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66072 2018-08-09T13:33:00 Z khohko Dungeon 2 (JOI16_dungeon2) C++17
44 / 100
 62 ms 49208 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[100];
ll pas[100];
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<10; 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 50 ms 47736 KB Output is correct
2 Correct 46 ms 47916 KB Output is correct
3 Correct 51 ms 47916 KB Output is correct
4 Correct 48 ms 47916 KB Output is correct
5 Correct 51 ms 47916 KB Output is correct
6 Correct 50 ms 47916 KB Output is correct
7 Correct 49 ms 47916 KB Output is correct
8 Correct 45 ms 47916 KB Output is correct
9 Correct 45 ms 47916 KB Output is correct
10 Correct 48 ms 47956 KB Output is correct
11 Correct 57 ms 48056 KB Output is correct
12 Correct 47 ms 48056 KB Output is correct
13 Correct 49 ms 48056 KB Output is correct
14 Correct 47 ms 48056 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 48056 KB Output is correct
2 Correct 52 ms 48056 KB Output is correct
3 Correct 53 ms 48056 KB Output is correct
4 Correct 52 ms 48056 KB Output is correct
5 Correct 49 ms 48084 KB Output is correct
6 Correct 45 ms 48084 KB Output is correct
7 Correct 44 ms 48084 KB Output is correct
8 Correct 51 ms 48084 KB Output is correct
9 Correct 47 ms 48084 KB Output is correct
10 Correct 48 ms 48084 KB Output is correct
11 Correct 47 ms 48084 KB Output is correct
12 Correct 52 ms 48084 KB Output is correct
13 Correct 53 ms 48084 KB Output is correct
14 Correct 62 ms 48084 KB Output is correct
15 Correct 51 ms 48084 KB Output is correct

Subtask #3
0 / 56.0

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