Submission #26244

#	Time	Username	Problem	Language	Result	Execution time	Memory
26244		kajebiii	Dungeon 2 (JOI16_dungeon2)	C++14	100 / 100	23 ms	3088 KiB

dungeon2

#include "dungeon2.h"
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 2e2 + 10;

int IN = 0;
vector<pi> Ed[MAX_N];
int P[MAX_N];

void dfs(int v) {
    int sz = NumberOfRoads();
    int last = LastRoad();
    for(int i=1; i<=sz; i++) {
        Move(i, 2);
        int c = Color();
        if(c == 2) {
            Ed[v].push_back(pi(0, 2));
            Move(LastRoad(), 2);
            continue;
        }
        if(c == 3) {
            Ed[v].push_back(pi(0, 3));
            Move(LastRoad(), 3);
            continue;
        }
        ++IN;
        P[IN] = v;
        Ed[v].push_back(pi(IN, 1));
        dfs(IN);
    }

    if(v != 1)
        Move(last, 3);
}

void findDfs(int v, int p, int c) {
    int last = LastRoad();
    for(int i=1; i<=Ed[v].size(); i++) {
        int &val = Ed[v][i-1].one, type = Ed[v][i-1].two;
        if(type == 3) continue;
        int nowC = (v / p) % 3 + 1;
        if(v != 1 && i == last) {
            val += (c-1) * p;
            continue;
        }
        Move(i, nowC);
//        printf("[v set %d]\n", (v / p) % 3 + 1);
        if(type == 2) {
            int c = Color();
            val += (c-1) * p;
            Move(LastRoad(), c);
            continue;
        }
        findDfs(val, p, nowC);
    }
    if(v != 1)
        Move(last, 1);
}
int N, Dis[MAX_N][MAX_N], Ans[MAX_N];
void Inspect(int R)
{
    ++IN;
    P[IN] = 0;
    dfs(IN);

    N = IN;
    for(int k=0, p=1; k<5; k++, p*=3) 
        findDfs(1, p, 0);

    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) 
        Dis[i][j] = INF;
    for(int i=1; i<=N; i++) for(pi x : Ed[i]) 
        Dis[i][x.one] = Dis[x.one][i] = 1;
    for(int i=1; i<=N; i++)
        Dis[i][i] = 0;
    for(int k=1; k<=N; k++) for(int i=1; i<=N; i++) for(int j=1; j<=N; j++)
        Dis[i][j] = min(Dis[i][j], Dis[i][k] + Dis[k][j]);
    for(int i=1; i<=N; i++) for(int j=i+1; j<=N; j++)
        Ans[Dis[i][j]]++;
    for(int i=1; i<=R; i++) 
        Answer(i, Ans[i]);
    return;
}

Compilation message (stderr)

dungeon2.cpp: In function 'void findDfs(int, int, int)':
dungeon2.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<=Ed[v].size(); i++) {
                   ^

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