Submission #69412

#	Time	Username	Problem	Language	Result	Execution time	Memory
69412		3zp	Dungeon 2 (JOI16_dungeon2)	C++14	44 / 100	4 ms	1484 KiB

dungeon2

#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 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;
        }
	}
    //cout<<k<<" "<<k1<<endl;
	//cout<<P<<endl;
	for(int i = 0; i < 5; i++){
        k = 0;
        N = 1;
        dfs2(1,i);

       // cout<<P1+P2+P3+P4<<" "<<P1<<" "<<P2<<" "<<P3<<" "<<P4<<endl;
        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);
       // cout<<V1[i].first<<" "<<V1[i].second<<endl;
    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);
      //  cout<<V[i].first<<" "<<V[i].second<<endl;
    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);//, cout<<ans[i]/2<<endl;
}

Compilation message (stderr)

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:112:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v[t].size(); i++)
                            ~~^~~~~~~~~~~~~

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