Submission #26134

#	Time	Username	Problem	Language	Result	Execution time	Memory
26134		kajebiii	Dungeon 2 (JOI16_dungeon2)	C++14	44 / 100	9 ms	2696 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<int> Ed[MAX_N]; int P[MAX_N], Ix[MAX_N], MemoIx[MAX_N], MemoV[MAX_N];
void dfs(int v) {
    int sz = NumberOfRoads();
    int last = LastRoad();
    Ix[v] = last;
    for(int i=1; i<=sz; i++) {
        if(i == last) continue;
        Move(i, 2);
        int c = Color();
        if(c == 2) {
            Move(LastRoad(), 3);
            int now = v, p, d = 0;
            while(true) {
                p = P[now]; d++;
                Move(Ix[now], 2);
                MemoIx[p] = LastRoad();
                MemoV[p] = now;
                now = p;

                if(Color() == 3) {
                    Ed[v].push_back(now);
                    Ed[now].push_back(v);
//                    printf("%d - %d\n", v, now);

                    for(int k=0; k<d; k++) {
                        Move(MemoIx[now], 2);
                        now = MemoV[now];
                    }
                    break;
                }
            }
            continue;
        }
        if(c == 3) {
            Move(LastRoad(), 3);
            continue;
        }
        ++IN;
        P[IN] = v;
        Ed[v].push_back(IN);
        Ed[IN].push_back(v);
//        printf("%d - %d\n", v, IN);
        dfs(IN);
    }

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

int N, Dis[MAX_N][MAX_N], Ans[MAX_N];
void Inspect(int R)
{
    ++IN;
    P[IN] = 0;
    dfs(IN);

    N = IN;

    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(int x : Ed[i])
        Dis[i][x] = 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;
}

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