| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 583221 |
2022-06-25T06:06:35 Z |
balbit |
Flights (JOI22_flights) |
C++17 |
|
71 ms |
2424 KB |
#include "Ali.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<ll, ll>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
namespace {
const int maxn = 1e4+2;
const int inf = 0x3f3f3f3f;
const int B = 15;
vector<int> g[maxn];
int dep[maxn];
vector<int> here[maxn]; // stuff in this group
vector<int> ord;
bool targ[maxn];
int who = -1;
int toid[maxn];
void dfs(int v, int p) {
ord.pb(v);
bool fc = 1;
for (int u : g[v]) {
if (u != p) {
dep[u] = dep[v] + 1;
dfs(u,v);
ord.pb(v);
}
}
}
void CLR(){
ord.clear();
memset(targ, 0, sizeof targ);
who = -1;
REP(i,maxn) {
g[i].clear(); dep[i] = 0; here[i].clear();
toid[i] = 0;
}
}
int finddst(int v, int p) {
if (targ[v]) {
who = v;
return 0;
}
int re = inf;
for (int u : g[v]) {
if (u == p) continue;
MN(re, 1+finddst(u,v));
}
return re;
}
int encode(pii p) {
assert(p.f <= p.s);
int re = 0;
REP(i, p.s) {
re += i+1;
}
re += p.f;
return re;
}
pii decode(int x) {
REP(i, 10000000) {
if (x < i+1) {
return {x,i};
}
x -= i+1;
}
assert(0);
}
}
#ifdef BALBIT
#endif // BALBIT
void Init(int N, std::vector<int> U, std::vector<int> V) {
// variable_example++;
// SetID(0, 0);
// SetID(1, 1);
// SetID(2, 2 * N + 19);
CLR();
REP(i, N-1) {
g[U[i]].pb(V[i]); g[V[i]].pb(U[i]);
}
dfs(0, -1);
memset(toid, -1, sizeof toid);
REP(i,SZ(ord)) {
here[i/B].pb(ord[i]);
if (toid[ord[i]] == -1) {
toid[ord[i]] = i;
}
}
REP(i,N) {
#ifdef BALBIT
bug(i, toid[i]);
#else
SetID(i, toid[i]);
#endif
}
}
std::string SendA(std::string S) {
assert(SZ(S) == 20);
ll tint = 0;
REP(i, SZ(S)) {
if (S[i] == '1') tint += (1<<i);
}
pii p = decode(tint);
int a = p.f, b = p.s;
bug(a, b);
#ifdef BALBIT
for (int e : here[a]) bug(e);
for (int e : here[b]) bug(e);
#endif // BALBIT
string ret;
int rta=-1, rtb=-1;
{
for (int t : here[a]) {
if (rta == -1 || dep[t] < dep[rta]) rta = t;
}
for (int t : here[b]) {
if (rtb == -1 || dep[t] < dep[rtb]) rtb = t;
}
}
// if (dep[rta] < dep[rta]) {
// ret += '0';
// }else{
// ret += '1';
// swap(a,b); swap(rta, rtb);
// // b has to be the deeper group!!
// }
REP1(i,B-1) {
if (i >= SZ(here[a])) {
ret+='1';
}else{
ret+= (dep[here[a][i]] > dep[here[a][i-1]]) + '0';
}
}
REP1(i,B-1) {
if (i >= SZ(here[b])) {
ret+='1';
}else{
ret+= (dep[here[b][i]] > dep[here[b][i-1]]) + '0';
}
}
{
int bestdst = inf;
pii bestpair = {-1, -1};
for (int t : here[b]) targ[t] = 1;
REP(i, SZ(here[a])) {
int e = here[a][i];
int ar = finddst(e, -1);
if (ar < bestdst) {
bestdst = ar;
int j = find(ALL(here[b]), who) - here[b].begin();
bestpair = {i,j};
}
}
REP(i,14) {
ret += '0' + ((bestdst >> i) & 1);
}
bug(bestdst, bestpair.f, bestpair.s);
REP(i,4) {
ret += '0' + ((bestpair.f >> i) & 1);
}
REP(i,4) {
ret += '0' + ((bestpair.s >> i) & 1);
}
}
return ret;
}
#ifdef BALBIT
signed main(){
int n = 9;
vector<int> u = {0,0,3,3,1,1,6,7};
vector<int> v = {3,6,2,1,5,7,8,4};
Init(n,u,v);
string ago = SendA("00100000000000000000");
bug(ago);
freopen("in", "w", stdout);
cout<<ago<<endl;
}
#endif
#include "Benjamin.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<ll, ll>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
namespace {
int variable_example = 0;
const int maxn = 1e4+2;
const int inf = 0x3f3f3f3f;
const int B = 15;
int X, Y;
int encode(pii p) {
assert(p.f <= p.s);
int re = 0;
REP(i, p.s) {
re += i+1;
}
re += p.f;
return re;
}
pii decode(int x) {
pii re = {0,0};
REP(i, 10000000) {
if (x < i+1) {
return {x,i};
}
x -= i+1;
}
}
vector<int> g[B*2];
int par[B*2];
int finddst(int v, int targ, int p) {
if (v==targ) {
return 0;
}
int re = inf;
for (int u : g[v]) {
if (u == p) continue;
MN(re, 1+finddst(u,targ,v));
}
return re;
}
int go(int gm, int p1, int p2) {
bug(gm, p1, p2);
memset(par, -1, sizeof par);
REP(i,B*2) g[i].clear();
int at = 0;
REP(i, B-1) {
if ((gm >> i) & 1) {
// go down
par[i+1] = at;
g[at].pb(i+1); g[i+1].pb(at);
at = i+1;
}else{
if (par[at] != -1) {
at = par[at];
}else{
par[at] = i+1;
g[at].pb(i+1); g[i+1].pb(at);
at = par[at];
}
}
}
return finddst(p1, p2, -1);
}
}
std::string SendB(int N, int _X, int _Y) {
X=_X; Y=_Y;
if (X > Y) swap(X,Y);
int a = X/B, b = Y/B;
int hey = encode({a,b});
assert(hey < (1<<20));
string re;
REP(i,20) {
re += '0' + ((hey>>i) & 1);
}
return re;
}
int Answer(std::string T) {
int at = 0;
auto read = [&](int nb) {
int re = 0;
REP(i,nb) {
if (T[at] == '1') re += (1<<i);
++at;
}
return re;
};
int g1 = read(B-1), g2 = read(B-1);
int dst = read(14);
int p1 = read(4), p2 = read(4);
bug(p1, p2);
if (X / B == Y / B) {
p1 = p2 = X%B; dst = 0;
}
int d1 = go(g1, p1, X%B);
int d2 = go(g2, p2, Y%B);
bug(d1);
bug(d2);
return d1 + d2 + dst;
}
#ifdef BALBIT
signed main(){
string bgo = SendB(9,5,14);
bug(bgo);
int yom = Answer("01111111111111111111111111111111110011111111111111");
bug(yom);
}
#endif
Compilation message
Ali.cpp: In function 'void {anonymous}::dfs(int, int)':
Ali.cpp:47:10: warning: unused variable 'fc' [-Wunused-variable]
47 | bool fc = 1;
| ^~
Ali.cpp: At global scope:
Ali.cpp:82:5: warning: 'int {anonymous}::encode(std::pair<long long int, long long int>)' defined but not used [-Wunused-function]
82 | int encode(pii p) {
| ^~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
10 | char _randmem[12379];
| ^~~~~~~~
Benjamin.cpp: In function 'std::pair<long long int, long long int> {anonymous}::decode(int)':
Benjamin.cpp:52:9: warning: variable 're' set but not used [-Wunused-but-set-variable]
52 | pii re = {0,0};
| ^~
Benjamin.cpp: At global scope:
Benjamin.cpp:51:5: warning: 'std::pair<long long int, long long int> {anonymous}::decode(int)' defined but not used [-Wunused-function]
51 | pii decode(int x) {
| ^~~~~~
Benjamin.cpp:34:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
34 | int variable_example = 0;
| ^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1040 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1040 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1128 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1040 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1040 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1904 KB |
Output is correct |
| 7 |
Correct |
11 ms |
1764 KB |
Output is correct |
| 8 |
Correct |
12 ms |
1752 KB |
Output is correct |
| 9 |
Correct |
11 ms |
1800 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1932 KB |
Output is correct |
| 11 |
Correct |
9 ms |
1640 KB |
Output is correct |
| 12 |
Correct |
8 ms |
1680 KB |
Output is correct |
| 13 |
Correct |
8 ms |
1772 KB |
Output is correct |
| 14 |
Correct |
8 ms |
1840 KB |
Output is correct |
| 15 |
Correct |
8 ms |
2412 KB |
Output is correct |
| 16 |
Correct |
9 ms |
1908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
3 ms |
1040 KB |
Output is partially correct |
| 2 |
Partially correct |
71 ms |
2424 KB |
Output is partially correct |
| 3 |
Incorrect |
2 ms |
856 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
