oj.uz

Submission #816836

# Submission time Handle Problem Language Result Execution time Memory
816836 2023-08-09T06:56:55 Z 이종영(#10379) Game (APIO22_game) C++17
2 / 100
 9 ms 14452 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N=3e5+5,H=22;
int n,k;
int d[N],p[N],lc[N],rc[N];
int in[N][H][2];
vector<int> g[N],gr[N];
int build(int h,int l,int r){
	if(l>r) return 0;
	int m=(l+r)>>1;
	d[m]=h;
	for(int i=l;i<=m;i++) in[i][h][0]=m;
	for(int i=m;i<=r;i++) in[i][h][1]=m;
	for(int i=h+1;i<H;i++) in[m][i][0]=in[m][i][1]=-1;
	if(l==r) return m;
	lc[m]=build(h+1,l,m-1);
	if(lc[m]) p[lc[m]]=m;
	rc[m]=build(h+1,m+1,r);
	if(rc[m]) p[rc[m]]=m;
	return m;
}
void init(int n_, int k_){
	n=n_;
	k=k_;
	for(int i=1;i<k;i++){
		g[i].emplace_back(i+1);
		gr[i+1].emplace_back(i);
	}
	lc[0]=rc[0]=build(1,1,k);
}
bool pos(int u,int m){
	if(m==lc[p[m]]) return in[u][d[p[m]]][0]==p[m];
	return in[u][d[p[m]]][1]==p[m];
}
bool dfs(int u,int m){
	in[u][d[m]][1]=m;
	//debug(u,d[m],1,m);
	if(in[u][d[m]][0]){
		debug(u); return 1;
	}
	for(int v: g[u]) if(pos(v,m)&&!in[u][d[m]][1]){
		if(dfs(v,m)) return 1;
	}
	return 0;
}
bool dfsr(int u,int m){
	in[u][d[m]][0]=m;
	//debug(u,d[m],0,m);
	if(in[u][d[m]][1]){
		debug(u); return 1;
	}
	for(int v: gr[u]) if(pos(v,m)&&!in[u][d[m]][0]){
		if(dfsr(v,m)) return 1;
	}
	return 0;
}
bool add(int l,int r,int u,int v){
	if(l>r) return 0;
	int m=(l+r)>>1;
	if(in[v][d[m]][0]==m&&pos(u,m)&&!in[u][d[m]][0]){
		if(dfsr(u,m)){
			debug(l,r,m,0); return 1;
		}
	}
	if(in[u][d[m]][1]==m&&pos(v,m)&&!in[v][d[m]][1]){
		if(dfs(v,m)){
			debug(l,r,m,1); return 1;
		}
	}
	if(in[u][d[m]][0]==m) return add(l,m-1,u,v);
	if(in[v][d[m]][1]==m) return add(m+1,r,u,v);
	return 0;
}
int add_teleporter(int u, int v){
	u++; v++;
	//debug(u,v);
	if(u==v&&u<=k) return 1;
	if(add(1,k,u,v)) return 1;
	g[u].emplace_back(v);
	gr[v].emplace_back(u);
	return 0;
}

Compilation message

game.cpp: In function 'bool dfs(int, int)':
game.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 42
      |                    ^~
game.cpp:45:3: note: in expansion of macro 'debug'
   45 |   debug(u); return 1;
      |   ^~~~~
game.cpp: In function 'bool dfsr(int, int)':
game.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 42
      |                    ^~
game.cpp:56:3: note: in expansion of macro 'debug'
   56 |   debug(u); return 1;
      |   ^~~~~
game.cpp: In function 'bool add(int, int, int, int)':
game.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 42
      |                    ^~
game.cpp:68:4: note: in expansion of macro 'debug'
   68 |    debug(l,r,m,0); return 1;
      |    ^~~~~
game.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 42
      |                    ^~
game.cpp:73:4: note: in expansion of macro 'debug'
   73 |    debug(l,r,m,1); return 1;
      |    ^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14416 KB Output is correct
2 Correct 7 ms 14328 KB Output is correct
3 Correct 7 ms 14452 KB Output is correct
4 Correct 9 ms 14324 KB Output is correct
5 Correct 7 ms 14348 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14416 KB Output is correct
2 Correct 7 ms 14328 KB Output is correct
3 Correct 7 ms 14452 KB Output is correct
4 Correct 9 ms 14324 KB Output is correct
5 Correct 7 ms 14348 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 6 ms 14416 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Correct 6 ms 14416 KB Output is correct
11 Incorrect 6 ms 14416 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14416 KB Output is correct
2 Correct 7 ms 14328 KB Output is correct
3 Correct 7 ms 14452 KB Output is correct
4 Correct 9 ms 14324 KB Output is correct
5 Correct 7 ms 14348 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 6 ms 14416 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Correct 6 ms 14416 KB Output is correct
11 Incorrect 6 ms 14416 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14416 KB Output is correct
2 Correct 7 ms 14328 KB Output is correct
3 Correct 7 ms 14452 KB Output is correct
4 Correct 9 ms 14324 KB Output is correct
5 Correct 7 ms 14348 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 6 ms 14416 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Correct 6 ms 14416 KB Output is correct
11 Incorrect 6 ms 14416 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14416 KB Output is correct
2 Correct 7 ms 14328 KB Output is correct
3 Correct 7 ms 14452 KB Output is correct
4 Correct 9 ms 14324 KB Output is correct
5 Correct 7 ms 14348 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 6 ms 14416 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Correct 6 ms 14416 KB Output is correct
11 Incorrect 6 ms 14416 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -