Submission #155686

#	Time	Username	Problem	Language	Result	Execution time	Memory
155686		TadijaSebez	Dungeon 2 (JOI16_dungeon2)	C++11	100 / 100	23 ms	1400 KiB

dungeon2

#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=205;
int tsz,par_edge[N],deg[N],par[N];
vector<pair<int,int>> tree_edges[N],other_edges[N];
vector<int> G[N];
void Build(int u)
{
	deg[u]=NumberOfRoads();
	par_edge[u]=LastRoad();
	for(int i=1;i<=deg[u];i++) if(i!=par_edge[u])
	{
		Move(i,3);
		int c=Color();
		if(c==3)
		{
			other_edges[u].pb({i,0});
			Move(LastRoad(),3);
		}
		else if(c==2)
		{
			Move(LastRoad(),2);
		}
		else
		{
			tsz++;
			par[tsz]=u;
			tree_edges[u].pb({i,tsz});
			Build(tsz);
		}
	}
	if(~par_edge[u]) Move(par_edge[u],2);
}
void DFS(int u, int dv)
{
	int cl=(u/dv)%3+1;
	for(auto e:tree_edges[u])
	{
		Move(e.first,cl);
		DFS(e.second,dv);
	}
	for(int i=0;i<other_edges[u].size();i++)
	{
        Move(other_edges[u][i].first,cl);
        int c=Color();
        other_edges[u][i].second+=(c-1)*dv;
        Move(LastRoad(),c);
	}
	if(~par_edge[u]) Move(par_edge[u],cl);
}
int dist[N],ans[N];
void BFS(int st)
{
	for(int i=1;i<=tsz;i++) dist[i]=1e9+7;
	dist[st]=0;
	queue<int> q;
	q.push(st);
	while(q.size())
	{
		int x=q.front();
		q.pop();
		for(int y:G[x])
		{
            if(dist[y]>dist[x]+1)
			{
				dist[y]=dist[x]+1;
				q.push(y);
			}
		}
	}
	for(int i=1;i<=tsz;i++) ans[dist[i]]++;
}
void AddEdge(int u, int v){ G[u].pb(v);G[v].pb(u);}
void Inspect(int R)
{
	tsz++;
	Build(tsz);
	for(int i=1;i<=200;i*=3) DFS(1,i);
	for(int i=1;i<=tsz;i++)
	{
		for(auto e:tree_edges[i]) AddEdge(i,e.second);
		for(auto e:other_edges[i]) AddEdge(i,e.second);
	}
	for(int i=1;i<=tsz;i++) BFS(i);
	for(int i=1;i<=R;i++) Answer(i,ans[i]/2);
}

Compilation message (stderr)

dungeon2.cpp: In function 'void DFS(int, int)':
dungeon2.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<other_edges[u].size();i++)
              ~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 27 / 27
• Subtask 3: 56 / 56