oj.uz

Submission #816650

# Submission time Handle Problem Language Result Execution time Memory
816650 2023-08-09T06:02:48 Z 이종영(#10379) Game (APIO22_game) C++17
2 / 100
 24 ms 42752 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;
set<int> S[N][2];
vector<int> g[N],gr[N];
void build(int l,int r){
	if(l>r) return;
	int m=(l+r)>>1;
	for(int i=l;i<=m;i++) S[m][0].emplace(i);
	for(int i=m;i<=r;i++) S[m][1].emplace(i);
	if(l==r) return;
	build(l,m-1); build(m+1,r);
}
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);
	}
	build(1,k);
}
bool dfs(int u,int m){
	debug(m,1,u);
	S[m][1].emplace(u);
	if(S[m][0].count(u)){
		debug(u); return 1;
	}
	for(int v: g[u]) if(!S[m][1].count(v)){
		if(dfs(v,m)) return 1;
	}
	return 0;
}
bool dfsr(int u,int m){
	debug(m,0,u);
	S[m][0].emplace(u);
	if(S[m][1].count(u)){
		debug(u); return 1;
	}
	for(int v: gr[u]) if(!S[m][0].count(v)){
		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(l==r) return 0;
	if(!S[m][0].count(u)&&S[m][0].count(v)){
		if(dfsr(u,m)){
			debug(l,r,m,0); return 1;
		}
	}
	if(S[m][1].count(u)&&!S[m][1].count(v)){
		if(dfs(v,m)){
			debug(l,r,m,1); return 1;
		}
	}
	if(S[m][0].count(u)) return add(l,m-1,u,v);
	if(S[m][1].count(u)) 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:31:2: note: in expansion of macro 'debug'
   31 |  debug(m,1,u);
      |  ^~~~~
game.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 42
      |                    ^~
game.cpp:34:3: note: in expansion of macro 'debug'
   34 |   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:42:2: note: in expansion of macro 'debug'
   42 |  debug(m,0,u);
      |  ^~~~~
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 add(int, int, int, int)':
game.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 42
      |                    ^~
game.cpp:58:4: note: in expansion of macro 'debug'
   58 |    debug(l,r,m,0); return 1;
      |    ^~~~~
game.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 42
      |                    ^~
game.cpp:63:4: note: in expansion of macro 'debug'
   63 |    debug(l,r,m,1); 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:72:2: note: in expansion of macro 'debug'
   72 |  debug(u,v);
      |  ^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42468 KB Output is correct
2 Correct 21 ms 42440 KB Output is correct
3 Correct 22 ms 42672 KB Output is correct
4 Correct 20 ms 42576 KB Output is correct
5 Correct 23 ms 42692 KB Output is correct
6 Correct 24 ms 42700 KB Output is correct
7 Correct 22 ms 42752 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42468 KB Output is correct
2 Correct 21 ms 42440 KB Output is correct
3 Correct 22 ms 42672 KB Output is correct
4 Correct 20 ms 42576 KB Output is correct
5 Correct 23 ms 42692 KB Output is correct
6 Correct 24 ms 42700 KB Output is correct
7 Correct 22 ms 42752 KB Output is correct
8 Correct 22 ms 42536 KB Output is correct
9 Correct 21 ms 42520 KB Output is correct
10 Correct 20 ms 42448 KB Output is correct
11 Correct 20 ms 42484 KB Output is correct
12 Correct 23 ms 42528 KB Output is correct
13 Incorrect 21 ms 42584 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42468 KB Output is correct
2 Correct 21 ms 42440 KB Output is correct
3 Correct 22 ms 42672 KB Output is correct
4 Correct 20 ms 42576 KB Output is correct
5 Correct 23 ms 42692 KB Output is correct
6 Correct 24 ms 42700 KB Output is correct
7 Correct 22 ms 42752 KB Output is correct
8 Correct 22 ms 42536 KB Output is correct
9 Correct 21 ms 42520 KB Output is correct
10 Correct 20 ms 42448 KB Output is correct
11 Correct 20 ms 42484 KB Output is correct
12 Correct 23 ms 42528 KB Output is correct
13 Incorrect 21 ms 42584 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42468 KB Output is correct
2 Correct 21 ms 42440 KB Output is correct
3 Correct 22 ms 42672 KB Output is correct
4 Correct 20 ms 42576 KB Output is correct
5 Correct 23 ms 42692 KB Output is correct
6 Correct 24 ms 42700 KB Output is correct
7 Correct 22 ms 42752 KB Output is correct
8 Correct 22 ms 42536 KB Output is correct
9 Correct 21 ms 42520 KB Output is correct
10 Correct 20 ms 42448 KB Output is correct
11 Correct 20 ms 42484 KB Output is correct
12 Correct 23 ms 42528 KB Output is correct
13 Incorrect 21 ms 42584 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42468 KB Output is correct
2 Correct 21 ms 42440 KB Output is correct
3 Correct 22 ms 42672 KB Output is correct
4 Correct 20 ms 42576 KB Output is correct
5 Correct 23 ms 42692 KB Output is correct
6 Correct 24 ms 42700 KB Output is correct
7 Correct 22 ms 42752 KB Output is correct
8 Correct 22 ms 42536 KB Output is correct
9 Correct 21 ms 42520 KB Output is correct
10 Correct 20 ms 42448 KB Output is correct
11 Correct 20 ms 42484 KB Output is correct
12 Correct 23 ms 42528 KB Output is correct
13 Incorrect 21 ms 42584 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -