oj.uz

Submission #66069

# Submission time Handle Problem Language Result Execution time Memory
66069 2018-08-09T13:29:01 Z khohko None (JOI16_dungeon2) C++17
44 / 100
 60 ms 49432 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) {

//	cout<<num()<<endl;
	//return;
	go(0);
//	for(int i=1; i<=n; i++){
//		cout<<i<<" = "<<nm[i]<<endl;
//		for(auto x:v[i])
//			cout<<x.fr<<" "<<x.sc<<endl;
//		cout<<endl;
//	}

//	cout<<num()<<endl;
	pw[0]=1;
	for(int i=1; i<10; i++)pw[i]=pw[i-1]*3;
	for(cr=0; cr<7; cr++){
		dfs(1);
		slv(1);
	}
//	cout<<endl;
//	cout<<endl;
//	cout<<"---------";
//	cout<<endl;
//	cout<<endl;
	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++){
//		cout<<nm[i]<<endl;
		for(int j=1; j<=nm[i]; j++){
//			cout<<f[i][j]<<" ";
			dp[i][f[i][j]]=1;
		}
//		cout<<endl;
	}
	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]]++;

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47740 KB Output is correct
2 Correct 47 ms 47848 KB Output is correct
3 Correct 50 ms 47848 KB Output is correct
4 Correct 47 ms 47912 KB Output is correct
5 Correct 45 ms 48116 KB Output is correct
6 Correct 51 ms 48116 KB Output is correct
7 Correct 55 ms 48140 KB Output is correct
8 Correct 49 ms 48140 KB Output is correct
9 Correct 46 ms 48140 KB Output is correct
10 Correct 50 ms 48140 KB Output is correct
11 Correct 44 ms 48140 KB Output is correct
12 Correct 49 ms 48164 KB Output is correct
13 Correct 48 ms 48164 KB Output is correct
14 Correct 55 ms 48164 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 48164 KB Output is correct
2 Correct 43 ms 48164 KB Output is correct
3 Correct 44 ms 48228 KB Output is correct
4 Correct 54 ms 48228 KB Output is correct
5 Correct 44 ms 48228 KB Output is correct
6 Correct 45 ms 48228 KB Output is correct
7 Correct 45 ms 48228 KB Output is correct
8 Correct 43 ms 48228 KB Output is correct
9 Correct 47 ms 48228 KB Output is correct
10 Correct 52 ms 48228 KB Output is correct
11 Correct 45 ms 48260 KB Output is correct
12 Correct 57 ms 48260 KB Output is correct
13 Correct 48 ms 48260 KB Output is correct
14 Correct 49 ms 48260 KB Output is correct
15 Correct 47 ms 48260 KB Output is correct

Subtask #3
0 / 56.0

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