| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 191978 |
2020-01-15T04:46:00 Z |
dndhk |
None (JOI16_dungeon2) |
C++14 |
|
2 ms |
732 KB |
#include "dungeon2.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 200;
const int INF = 1000;
vector<pii> gp[MAX_N+1];
vector<int> gp2[MAX_N+1];
vector<int> to[MAX_N+1];
vector<int> s[MAX_N+1], e[MAX_N+1];
pii p[MAX_N+1];
int deg[MAX_N+1];
int N = 1;
bool chk[MAX_N+1];
void dfs1(int x){
//cout<<x<<endl;
deg[x] = NumberOfRoads();
for(int i=0; i<=deg[x]; i++){
to[x].pb(0);
s[x].pb(0); e[x].pb(0);
}
if(x!=1){
p[x].second = LastRoad();
to[x][p[x].second] = p[x].first;
}
for(int i=1; i<=deg[x]; i++){
if(to[x][i]==0){
Move(i, x+1);
int c = Color();
int t = LastRoad();
if(c==1){
N++;
p[N].first = x;
gp2[x].pb(N);
gp2[N].pb(x);
to[x][i] = N;
dfs1(N);
Move(p[to[x][i]].second, to[x][i]+1);
}/*else if(c==2){
to[x][i] = -1;
Move(LastRoad(), 2);
}else{
to[x][i] = -2;
Move(LastRoad(), 3);
}*/
else{
if(c<x+1){
gp2[c-1].pb(x);
gp2[x].pb(c-1);
}
Move(LastRoad(), c);
}
}
}
}
void dfs2(int x){
//cout<<x<<endl;
for(int i=1; i<=deg[x]; i++){
if(to[x][i]==p[x].first) continue;
if(to[x][i]==-2) continue;
if(to[x][i]==-1){
Move(i, 1);
int c = Color();
if(c==2){
s[x][i] = (s[x][i]+e[x][i])/2+1;
}else{
e[x][i] = (s[x][i]+e[x][i])/2;
}
Move(LastRoad(), c);
if(s[x][i]==e[x][i]){
gp2[x].pb(s[x][i]);
gp2[s[x][i]].pb(x);
to[x][i] = -2;
}
}else{
if(chk[x]){
Move(i, 3);
dfs2(to[x][i]);
Move(p[to[x][i]].second, 1);
}else{
Move(i, 2);
dfs2(to[x][i]);
Move(p[to[x][i]].second, 1);
}
}
}
}
vector<pii> v1, v2;
int dist[MAX_N+1];
int ans[MAX_N+1];
deque<int> dq;
void bfs(int x){
dq.pb(x);
dist[x] = 0;
while(!dq.empty()){
int now = dq.front(); dq.pop_front();
for(int i : gp2[now]){
if(dist[i]>dist[now]+1){
dist[i] = dist[now]+1;
dq.pb(i);
}
}
}
}
void Inspect(int R){
dfs1(1);
//v1.pb({1, N});
for(int i=1; i<=N; i++){
for(int j=1; j<=deg[i]; j++){
if(to[i][j]==-1){
s[i][j] = 1;
e[i][j] = N;
}
}
}
while(!v1.empty()){
for(pii p : v1){
if(p.first!=p.second){
v2.pb({p.first, (p.first+p.second)/2});
v2.pb({(p.first+p.second)/2+1, p.second});
}
}
while(!v1.empty()) v1.pop_back();
for(pii p : v2){
v1.pb(p);
}
while(!v2.empty()) v2.pop_back();
for(int i=1; i<=N; i++){
chk[i] = false;
}
if(v1.empty()) break;
for(int i=0; i<v1.size(); i+=2){
pii p = v1[i];
for(int j=p.first; j<=p.second; j++){
chk[j] = true;
}
}
dfs2(1);
}
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
dist[j] = INF;
}
bfs(i);
//cout<<i<<endl;
for(int j=1; j<=N; j++){
//cout<<j<<" "<<dist[j]<<endl;
if(dist[j]!=0){
ans[dist[j]]++;
}
}
}
for(int i=1; i<=R; i++){
//cout<<i<<" "<<ans[i]<<endl;
if(R<=N){
Answer(i, ans[i]/2);
}else{
Answer(i, 0);
}
}
}
Compilation message
dungeon2.cpp: In function 'void dfs1(int)':
dungeon2.cpp:39:8: warning: unused variable 't' [-Wunused-variable]
int t = LastRoad();
^
dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:147:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v1.size(); i+=2){
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
380 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
504 KB |
Wrong Answer [4] |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
316 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
732 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
