oj.uz

Submission #66070

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

//	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<15; i++)pw[i]=pw[i-1]*3;
	for(cr=0; cr<9; 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 47 ms 47736 KB Output is correct
2 Correct 48 ms 47736 KB Output is correct
3 Correct 51 ms 47792 KB Output is correct
4 Correct 44 ms 47792 KB Output is correct
5 Correct 44 ms 47868 KB Output is correct
6 Correct 43 ms 47868 KB Output is correct
7 Correct 48 ms 48032 KB Output is correct
8 Correct 43 ms 48032 KB Output is correct
9 Correct 48 ms 48032 KB Output is correct
10 Correct 60 ms 48032 KB Output is correct
11 Correct 59 ms 48032 KB Output is correct
12 Correct 47 ms 48032 KB Output is correct
13 Correct 51 ms 48032 KB Output is correct
14 Correct 51 ms 48040 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 48040 KB Output is correct
2 Correct 50 ms 48040 KB Output is correct
3 Correct 45 ms 48040 KB Output is correct
4 Correct 44 ms 48040 KB Output is correct
5 Correct 49 ms 48056 KB Output is correct
6 Correct 45 ms 48056 KB Output is correct
7 Correct 45 ms 48056 KB Output is correct
8 Correct 43 ms 48056 KB Output is correct
9 Correct 46 ms 48056 KB Output is correct
10 Correct 49 ms 48056 KB Output is correct
11 Correct 50 ms 48108 KB Output is correct
12 Correct 49 ms 48108 KB Output is correct
13 Correct 45 ms 48108 KB Output is correct
14 Correct 45 ms 48108 KB Output is correct
15 Correct 59 ms 48108 KB Output is correct

Subtask #3
0 / 56.0

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