oj.uz

Submission #66086

# Submission time Handle Problem Language Result Execution time Memory
66086 2018-08-09T14:02:57 Z khohko None (JOI16_dungeon2) C++17
44 / 100
 18 ms 3052 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 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++){
		if(ef[x][i])continue;
		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);

	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;
	for(cr=0; cr<4; 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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 3 ms 996 KB Output is correct
3 Correct 4 ms 1032 KB Output is correct
4 Correct 4 ms 1080 KB Output is correct
5 Correct 3 ms 1132 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 4 ms 1156 KB Output is correct
8 Correct 4 ms 1156 KB Output is correct
9 Correct 3 ms 1156 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 4 ms 1236 KB Output is correct
12 Correct 3 ms 1236 KB Output is correct
13 Correct 3 ms 1240 KB Output is correct
14 Correct 3 ms 1240 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1240 KB Output is correct
2 Correct 3 ms 1240 KB Output is correct
3 Correct 4 ms 1356 KB Output is correct
4 Correct 3 ms 1356 KB Output is correct
5 Correct 4 ms 1356 KB Output is correct
6 Correct 3 ms 1356 KB Output is correct
7 Correct 3 ms 1356 KB Output is correct
8 Correct 4 ms 1356 KB Output is correct
9 Correct 4 ms 1356 KB Output is correct
10 Correct 4 ms 1356 KB Output is correct
11 Correct 4 ms 1356 KB Output is correct
12 Correct 3 ms 1356 KB Output is correct
13 Correct 3 ms 1364 KB Output is correct
14 Correct 4 ms 1364 KB Output is correct
15 Correct 3 ms 1364 KB Output is correct

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 3052 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -