oj.uz

Submission #816997

# Submission time Handle Problem Language Result Execution time Memory
816997 2023-08-09T08:18:23 Z 이종영(#10379) Game (APIO22_game) C++17
2 / 100
 15 ms 28576 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=30;
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);
}
vector<int> wait[N][2];
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 dfsr(int u,int m){
	if(in[u][d[m]][0]) return 0;
	in[u][d[m]][0]=m;
	debug(u,d[m],0,m);
	if(in[u][d[m]][1]){
		debug(u); return 1;
	}
	if(lc[m]){
		for(int v: g[u]) if(in[v][d[m]+1][0]==lc[m]) wait[lc[m]][0].emplace_back(u);
		for(int v: gr[u]) if(in[v][d[m]+1][1]==lc[m]) wait[lc[m]][1].emplace_back(u);
	}
	for(int v: gr[u]) if(pos(v,m)){
		if(dfsr(v,m)) return 1;
	}
	return 0;
}
bool dfs(int u,int m){
	if(in[u][d[m]][1]) return 0;
	in[u][d[m]][1]=m;
	debug(u,d[m],1,m);
	if(in[u][d[m]][0]){
		debug(u); return 1;
	}
	if(rc[m]){
		for(int v: g[u]) if(in[v][d[m]+1][0]==rc[m]) wait[rc[m]][0].emplace_back(u);
		for(int v: gr[u]) if(in[v][d[m]+1][1]==rc[m]) wait[rc[m]][1].emplace_back(u);
	}
	for(int v: g[u]) if(pos(v,m)){
		if(dfs(v,m)) return 1;
	}
	return 0;
}
bool add(int m,int c){
	if(!wait[m][c].size()) return 0;
	if(!c){
		for(int u: wait[m][0]) if(dfsr(u,m)) return 1;
		if(add(lc[m],0)) return 1;
		if(add(lc[m],1)) return 1;
	} else{
		for(int u: wait[m][1]) if(dfs(u,m)) return 1;
		if(add(rc[m],0)) return 1;
		if(add(rc[m],1)) return 1;
	}
	return 0;
}
bool add1(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){
		if(u==m) return 1;
		if(!in[u][d[m]][0]){
			wait[m][0].emplace_back(u);
			return add(m,0);
		}
	}
	if(in[u][d[m]][0]==m&&in[v][d[m]][0]==m) return add1(l,m-1,u,v);
	if(in[u][d[m]][1]==m&&in[v][d[m]][1]==m) return add1(m+1,r,u,v);
	return 0;
}
bool add2(int l,int r,int u,int v){
	if(l>r) return 0;
	int m=(l+r)>>1;
	if(in[u][d[m]][1]==m){
		if(v==m) return 1;
		if(!in[v][d[m]][1]){
			wait[m][1].emplace_back(v);
			return add(m,1);
		}
	}
	if(in[u][d[m]][0]==m&&in[v][d[m]][0]==m) return add1(l,m-1,u,v);
	if(in[u][d[m]][1]==m&&in[v][d[m]][1]==m) return add1(m+1,r,u,v);
	return 0;
}
int add_teleporter(int u, int v){
	u++; v++;
	debug(u,v);
	g[u].emplace_back(v);
	gr[v].emplace_back(u);
	if(add1(1,k,u,v)) return 1;
	if(add2(1,k,u,v)) return 1;
	return 0;
}

Compilation message

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:45:2: note: in expansion of macro 'debug'
   45 |  debug(u,d[m],0,m);
      |  ^~~~~
game.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 42
      |                    ^~
game.cpp:47:3: note: in expansion of macro 'debug'
   47 |   debug(u); return 1;
      |   ^~~~~
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:61:2: note: in expansion of macro 'debug'
   61 |  debug(u,d[m],1,m);
      |  ^~~~~
game.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 42
      |                    ^~
game.cpp:63:3: note: in expansion of macro 'debug'
   63 |   debug(u); return 1;
      |   ^~~~~
game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 42
      |                    ^~
game.cpp:117:2: note: in expansion of macro 'debug'
  117 |  debug(u,v);
      |  ^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28496 KB Output is correct
2 Correct 15 ms 28544 KB Output is correct
3 Correct 13 ms 28576 KB Output is correct
4 Correct 13 ms 28416 KB Output is correct
5 Correct 14 ms 28496 KB Output is correct
6 Correct 14 ms 28524 KB Output is correct
7 Correct 15 ms 28496 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28496 KB Output is correct
2 Correct 15 ms 28544 KB Output is correct
3 Correct 13 ms 28576 KB Output is correct
4 Correct 13 ms 28416 KB Output is correct
5 Correct 14 ms 28496 KB Output is correct
6 Correct 14 ms 28524 KB Output is correct
7 Correct 15 ms 28496 KB Output is correct
8 Correct 13 ms 28496 KB Output is correct
9 Correct 13 ms 28496 KB Output is correct
10 Correct 12 ms 28496 KB Output is correct
11 Correct 13 ms 28544 KB Output is correct
12 Correct 14 ms 28436 KB Output is correct
13 Incorrect 13 ms 28528 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28496 KB Output is correct
2 Correct 15 ms 28544 KB Output is correct
3 Correct 13 ms 28576 KB Output is correct
4 Correct 13 ms 28416 KB Output is correct
5 Correct 14 ms 28496 KB Output is correct
6 Correct 14 ms 28524 KB Output is correct
7 Correct 15 ms 28496 KB Output is correct
8 Correct 13 ms 28496 KB Output is correct
9 Correct 13 ms 28496 KB Output is correct
10 Correct 12 ms 28496 KB Output is correct
11 Correct 13 ms 28544 KB Output is correct
12 Correct 14 ms 28436 KB Output is correct
13 Incorrect 13 ms 28528 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28496 KB Output is correct
2 Correct 15 ms 28544 KB Output is correct
3 Correct 13 ms 28576 KB Output is correct
4 Correct 13 ms 28416 KB Output is correct
5 Correct 14 ms 28496 KB Output is correct
6 Correct 14 ms 28524 KB Output is correct
7 Correct 15 ms 28496 KB Output is correct
8 Correct 13 ms 28496 KB Output is correct
9 Correct 13 ms 28496 KB Output is correct
10 Correct 12 ms 28496 KB Output is correct
11 Correct 13 ms 28544 KB Output is correct
12 Correct 14 ms 28436 KB Output is correct
13 Incorrect 13 ms 28528 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28496 KB Output is correct
2 Correct 15 ms 28544 KB Output is correct
3 Correct 13 ms 28576 KB Output is correct
4 Correct 13 ms 28416 KB Output is correct
5 Correct 14 ms 28496 KB Output is correct
6 Correct 14 ms 28524 KB Output is correct
7 Correct 15 ms 28496 KB Output is correct
8 Correct 13 ms 28496 KB Output is correct
9 Correct 13 ms 28496 KB Output is correct
10 Correct 12 ms 28496 KB Output is correct
11 Correct 13 ms 28544 KB Output is correct
12 Correct 14 ms 28436 KB Output is correct
13 Incorrect 13 ms 28528 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -