oj.uz

Submission #26213

# Submission time Handle Problem Language Result Execution time Memory
26213 2017-06-28T11:25:16 Z kajebiii None (JOI16_dungeon2) C++14
90 / 100
 23 ms 3088 KB 
#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 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;
        Move(i, (v / p) % 3 + 1);
//        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);
    }
    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);

    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

dungeon2.cpp: In function 'void findDfs(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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2692 KB Output is correct
2 Correct 0 ms 2692 KB Output is correct
3 Correct 0 ms 2692 KB Output is correct
4 Correct 0 ms 2692 KB Output is correct
5 Correct 0 ms 2692 KB Output is correct
6 Correct 0 ms 2692 KB Output is correct
7 Correct 0 ms 2692 KB Output is correct
8 Correct 0 ms 2692 KB Output is correct
9 Correct 0 ms 2692 KB Output is correct
10 Correct 0 ms 2692 KB Output is correct
11 Correct 0 ms 2692 KB Output is correct
12 Correct 0 ms 2692 KB Output is correct
13 Correct 0 ms 2692 KB Output is correct
14 Correct 0 ms 2692 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2692 KB Output is correct
2 Correct 0 ms 2692 KB Output is correct
3 Correct 0 ms 2692 KB Output is correct
4 Correct 0 ms 2692 KB Output is correct
5 Correct 0 ms 2692 KB Output is correct
6 Correct 0 ms 2692 KB Output is correct
7 Correct 0 ms 2692 KB Output is correct
8 Correct 0 ms 2692 KB Output is correct
9 Correct 0 ms 2692 KB Output is correct
10 Correct 0 ms 2692 KB Output is correct
11 Correct 0 ms 2692 KB Output is correct
12 Correct 0 ms 2692 KB Output is correct
13 Correct 0 ms 2692 KB Output is correct
14 Correct 0 ms 2692 KB Output is correct
15 Correct 0 ms 2692 KB Output is correct

Subtask #3
46.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 2692 KB Partially correct
2 Partially correct 9 ms 2692 KB Partially correct
3 Partially correct 9 ms 2692 KB Partially correct
4 Partially correct 23 ms 3088 KB Partially correct
5 Partially correct 0 ms 2692 KB Partially correct
6 Partially correct 3 ms 2692 KB Partially correct
7 Partially correct 9 ms 2692 KB Partially correct
8 Partially correct 9 ms 2692 KB Partially correct
9 Partially correct 9 ms 2692 KB Partially correct
10 Partially correct 9 ms 2692 KB Partially correct
11 Partially correct 9 ms 2692 KB Partially correct
12 Partially correct 9 ms 2692 KB Partially correct
13 Partially correct 13 ms 2824 KB Partially correct
14 Partially correct 9 ms 2692 KB Partially correct
15 Partially correct 9 ms 2692 KB Partially correct
16 Partially correct 3 ms 2824 KB Partially correct
17 Partially correct 23 ms 3088 KB Partially correct
18 Partially correct 19 ms 3088 KB Partially correct
19 Partially correct 16 ms 3088 KB Partially correct