oj.uz

Submission #26179

# Submission time Handle Problem Language Result Execution time Memory
26179 2017-06-28T08:32:36 Z 시제연(#1098) None (JOI16_dungeon2) C++
44 / 100
 16 ms 2848 KB 
#include "dungeon2.h"
#include <bits/stdc++.h>

using namespace std;

/*
void Answer(int D, int A)
void Move(int I, int C)
int NumberOfRoads()
int LastRoad()
int Color()
*/

vector<int> name[220];
vector<int> bck[220];
vector<int> nis;
int n;
void dfs(int here, int par) {
    int sz = NumberOfRoads(), p = LastRoad(), q, i;
    if (~par) {
        bck[here].push_back(p);
        for (i=0;i<bck[par].size();i++) bck[here].push_back(bck[par][i]);
    }
    name[here].assign(nis.begin(),nis.end());
    for (i=1;i<=sz;i++) {
        if (i==p) continue;
        Move(i,2); q = LastRoad();
        if (Color()!=2) {
            nis.push_back(i);
            n++;
            dfs(n-1,here);
            nis.pop_back();
        }
        Move(q,2);
    }
}

int curpos;

void go(int idx) {
    int i;
    for (i=0;i<name[idx].size();i++) Move(name[idx][i],Color());
}

bool chk() {
    int sz = NumberOfRoads(), q, i;
    bool flag = false;
    for (i=1;i<=sz;i++) {
        Move(i,Color()); q = LastRoad();
        if (Color()==3) flag = true;
        Move(q,Color());
    }
    return flag;
}

void colba(int idx, int col) {
    int i;
    if (idx==0) {
        Move(1,col); int q = LastRoad(); Move(q,Color()); return;
    }
    Move(bck[idx][0],col);
    for (i=1;i<bck[idx].size();i++) Move(bck[idx][i],Color());
}

void ba(int idx) {
    colba(idx,2);
}

void init() {
    n++;
    dfs(n-1,-1);
    /*
    int i, j;
    for (i=0;i<n;i++) {
        for (j=0;j<name[i].size();j++) printf("%d ",name[i][j]);
        printf("\n");
        for (j=0;j<bck[i].size();j++) printf("%d ",bck[i][j]);
        printf("\n");
    }
    */
}

const int INF = 987654321;
int mat[220][220];
int res[220];

void floyd() {
    int i, j, k;
    for (k=0;k<n;k++) {
        for (i=0;i<n;i++) {
            for (j=0;j<n;j++) {
                if (mat[i][j]>mat[i][k]+mat[k][j]) {
                    mat[i][j]=mat[i][k]+mat[k][j];
                }
            }
        }
    }
    for (i=0;i<n;i++) for (j=i+1;j<n;j++) if (mat[i][j]<=n) res[mat[i][j]]++;
}

void Inspect(int R) {
	int i, j;
	init();
	for (i=0;i<n;i++) for (j=0;j<n;j++) if (i!=j) mat[i][j] = INF;
	for (i=0;i<n;i++) {
        go(i);
        colba(i,3);
        for (j=i+1;j<n;j++) {
            go(j);
            if (chk()) {mat[i][j]=mat[j][i]=1;};
            ba(j);
        }
        go(i);
        ba(i);
	}
	floyd();
	for (i=1;i<=R;i++) Answer(i,res[i]);
}

Compilation message

dungeon2.cpp: In function 'void dfs(int, int)':
dungeon2.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<bck[par].size();i++) bck[here].push_back(bck[par][i]);
                   ^
dungeon2.cpp: In function 'void go(int)':
dungeon2.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<name[idx].size();i++) Move(name[idx][i],Color());
               ^
dungeon2.cpp: In function 'void colba(int, int)':
dungeon2.cpp:62:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=1;i<bck[idx].size();i++) Move(bck[idx][i],Color());
               ^

Subtask #1
17.0 / 17.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2848 KB Output isn't correct
2 Halted 0 ms 0 KB -