oj.uz

Submission #69413

# Submission time Handle Problem Language Result Execution time Memory
69413 2018-08-20T19:35:43 Z 3zp None (JOI16_dungeon2) C++14
100 / 100
 29 ms 3048 KB 
#include "dungeon2.h"
#include<bits/stdc++.h>
using namespace std;
pair<int,int> V[20009],V1[20009];
int f[209][209];
int d[209];
int B[250][6];
vector<int> v[10009];
int ans[100009];
int F[10009];
int D[10009];
int P = 0,P1=0,P2=0,P3=0,P4=0;
int k, k1;
int N = 1;
void dfs1(int x){
    d[x] = NumberOfRoads();
    int p = LastRoad();
    int down = 0;
    int q;
    for(int i = 1; i <= d[x]; i++){
        if(i == p) continue;
        P1++;Move(i,2);
        down = 1;
        q = LastRoad();
        if(Color() == 1){
            V1[k1]= {x, ++N};
            k1++;
            dfs1(N);
            f[x][i] = 2;
            P2++;Move(q, 3);

        }
        else
        if(Color() == 2){
            V[k] = {x, 0};
            k++;
            f[x][i] = 1;
            P3++;Move(q, Color());
        }
        else{
            P4++;Move(q, Color());
        }
    }
   // if(down) P++;Move(q, 3);
}
void dfs2(int x, int b){
    int p = LastRoad();
    if(x == 1) p = -1;
    for(int i = 1; i <= d[x]; i++){
        if(i == p) continue;
        if(f[x][i] == 0) continue;
             P1++;
        Move(i,B[x][b]);
        int q = LastRoad();

        if(f[x][i] == 2){
            int T = N+1;
            dfs2(++N, b);
            P2++;Move(q, B[T][b]);
        }
        else
        if(f[x][i] == 1){
            V[k].second *=3;
            V[k].second += Color()-1;

            k++;
            P3++;Move(q, Color());
        }
        else
            {P4++;Move(q, Color());}
    }
}
void Inspect(int R)
{
	dfs1(1);
	for(int i = 0; i < 243; i++){
        int x = i;
        for(int j = 0; j < 5; j++){
            B[i][4-j] = x % 3 + 1;
            x /= 3;
        }
	}
	for(int i = 0; i < 5; i++){
        k = 0;
        N = 1;
        dfs2(1,i);
        P = 0, P1=0,P2=0,P3=0,P4=0;
	}

	for(int i = 0; i < k1; i++)
        v[V1[i].first].push_back(V1[i].second),
        v[V1[i].second].push_back(V1[i].first);
    for(int i = 0; i < k; i++)
        v[V[i].first].push_back(V[i].second),
        v[V[i].second].push_back(V[i].first);
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++)
            F[j] = 0, D[j] = 0;
        F[i] = 1;
        queue<int> Q;
        Q.push(i);
        while(Q.size()){
            int t = Q.front();
            ans[D[t]] ++;
            Q.pop();
            for(int i = 0; i < v[t].size(); i++)
            if(F[v[t][i]] == 0){
                Q.push(v[t][i]);
                D[v[t][i]] = D[t]+1;
                F[v[t][i]] = 1;
            }
        }
    }

        for(int i = 1; i <= R; i++)
            Answer(i,ans[i]/2);
}

Compilation message

dungeon2.cpp: In function 'void dfs1(int)':
dungeon2.cpp:18:9: warning: variable 'down' set but not used [-Wunused-but-set-variable]
     int down = 0;
         ^~~~
dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:106:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v[t].size(); i++)
                            ~~^~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1404 KB Output is correct
2 Correct 6 ms 1404 KB Output is correct
3 Correct 6 ms 1412 KB Output is correct
4 Correct 29 ms 2176 KB Output is correct
5 Correct 5 ms 2176 KB Output is correct
6 Correct 5 ms 2176 KB Output is correct
7 Correct 4 ms 2176 KB Output is correct
8 Correct 4 ms 2176 KB Output is correct
9 Correct 5 ms 2176 KB Output is correct
10 Correct 4 ms 2176 KB Output is correct
11 Correct 4 ms 2176 KB Output is correct
12 Correct 4 ms 2176 KB Output is correct
13 Correct 8 ms 2176 KB Output is correct
14 Correct 4 ms 2176 KB Output is correct
15 Correct 4 ms 2176 KB Output is correct
16 Correct 7 ms 2176 KB Output is correct
17 Correct 26 ms 2724 KB Output is correct
18 Correct 27 ms 2808 KB Output is correct
19 Correct 28 ms 3048 KB Output is correct