oj.uz

Submission #26244

# Submission time Handle Problem Language Result Execution time Memory
26244 2017-06-28T13:33:42 Z kajebiii None (JOI16_dungeon2) C++14
100 / 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 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

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.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
56.0 / 56.0

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