Submission #69389

# Submission time Handle Problem Language Result Execution time Memory
69389 2018-08-20T17:41:30 Z 3zp None (JOI16_dungeon2) C++14
0 / 100
3 ms 1116 KB
#include "dungeon2.h"
#include<bits/stdc++.h>
using namespace std;
pair<int,int> V[100009],V1[100009];
int f[109][109];
int d[109];
int B[250][6];
vector<int> v[10009];
int ans[100009];
int F[10009];
int D[10009];
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;
        Move(i,2);
        down = 1;
        q = LastRoad();
        if(Color() == 1){
            V1[k1]= {x, ++N};
            k1++;
            dfs1(N);
            f[x][i] = 2;
            Move(q, 3);
        }
        else
        if(Color() == 2){
            V[k] = {x, 0};
            k++;
            f[x][i] = 1;
            Move(q, Color());
        }
        else{
            Move(q, Color());
        }
    }
   // if(down) Move(q, 3);
}
void dfs2(int x, int b){
    int p = LastRoad();
    for(int i = 1; i <= d[x]; i++){
        if(i == p) continue;
        Move(i,B[x][b]);
        int q = LastRoad();

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

            k++;
            Move(q, Color());
        }
        else
            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);
	}

	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:17:9: warning: variable 'down' set but not used [-Wunused-but-set-variable]
     int down = 0;
         ^~~~
dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:100:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v[t].size(); i++)
                            ~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 760 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Incorrect 3 ms 912 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1116 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -