| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 566197 |
2022-05-22T05:33:16 Z |
8e7 |
Flights (JOI22_flights) |
C++17 |
|
302 ms |
2880 KB |
//Challenge: Accepted
#include "Ali.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 10005
#define pii pair<int, int>
#define ff first
#define ss second
const int bs = 10;
vector<int> adj[maxn];
int bid[maxn], bord[maxn], siz[maxn], par[maxn], dep[maxn], id[maxn];
bool isroot[maxn];
int root[maxn];
string trav[maxn];
int C = 0;
int st;
void dfs(int n, int pa, int d) {
par[n] = pa;
dep[n] = d;
siz[n] = 1;
debug(n);
for (int v:adj[n]) {
if (v != pa) {
dfs(v, n, d+1);
if (siz[v] < bs) {
siz[n] += siz[v];
}
}
}
if (siz[n] >= bs || n == st) {
debug("root", n, siz[n]);
isroot[n] = 1;
bid[n] = C;
root[C++] = n;
}
}
void getb(int n, int pa, int &ti) {
bord[n] = ti++;
for (int v:adj[n]) {
if (v != pa && !isroot[v]) {
trav[bid[n]] += '1';
bid[v] = bid[n];
getb(v, n, ti);
trav[bid[n]] += '0';
}
}
}
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
for (int i = 0;i < N;i++) {
adj[i].clear();
trav[i].clear();
bid[i] = 0, bord[i] = 0;
siz[i] = 0;
isroot[i] = 0, root[i] = 0;
}
C = 0;
for (int i = 0;i < N - 1;i++) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
for (int i = 0;i < N;i++) {
if (adj[i].size() == 1) {
st = i;
dfs(st, -1, 0);
break;
}
}
for (int i = 0;i < N;i++) {
if (isroot[i]) {
int tmp = 0;
getb(i, par[i], tmp);
}
}
for (int i = 0;i < C;i++) {
while (trav[i].size() < 36) trav[i] += '0';
}
for (int i = 0;i < N;i++) {
id[i] = bid[i] * 2 * bs + bord[i];
//debug(bid[i], bord[i]);
SetID(i, id[i]);
}
}
std::string SendA(std::string S) {
int bx = 0, by = 0;
for (int i = 0;i < 10;i++) bx += (S[i] - '0') * (1<<i);
for (int i = 10;i < 20;i++) by += (S[i] - '0') * (1<<(i-10));
debug("senda", bx, by);
int dis = 0;
int px = root[bx], py = root[by], v = 0;
while (px != py) {
if (dep[px] < dep[py]) swap(px, py);
px = par[px];
dis++;
if (bid[px] == bid[py] && bid[px] == bx) {
v = bord[px];
break;
}
}
debug(dis);
string ret;
for (int i = 0;i < 14;i++) ret += char(((dis >> i) & 1) + '0');
ret.insert(ret.end(), trav[bx].begin(), trav[bx].end());
ret.insert(ret.end(), trav[by].begin(), trav[by].end());
for (int i = 0;i < 5;i++) ret += char(((v >> i) & 1) + '0');
debug(ret);
return ret;
}
//Challenge: Accepted
#include "Benjamin.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 10005
#define pii pair<int, int>
#define ff first
#define ss second
namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
const int bs = 10;
int bx, by, dx, dy;
int par[maxn], dep[maxn];
void decode(string s) {
int d = 0, cur = 0, id = 0;
dep[cur] = 0;
for (auto i:s) {
d += (i == '1' ? 1 : -1);
if (i - '0') {
dep[++id] = d;
par[id] = cur;
cur = id;
} else {
if (d < 0) return;
cur = par[cur];
}
}
}
}
std::string SendB(int N, int X, int Y) {
bx = X / (2 * bs), by = Y / (2 * bs);
dx = X % (2 * bs), dy = Y % (2 * bs);
if (bx < by) swap(bx, by), swap(dx, dy);
string ret;
for (int i = 0;i < 10;i++) ret += char(((bx >> i) & 1) + '0');
for (int i = 0;i < 10;i++) ret += char(((by >> i) & 1) + '0');
debug(bx, dx, by, dy);
return ret;
}
int Answer(std::string T) {
int ret = 0;
for (int i = 0;i < 14;i++) {
ret += (1<<i) * (T[i] - '0');
}
if (bx != by) {
decode(T.substr(14, 36));
int v = 0;
for (int i = 0;i < 5;i++) v += (1<<i) * (T[86 + i] - '0');
if (v) {
while (dx != v) {
if (dep[dx] < dep[v]) swap(dx, v);
dx = par[dx];
ret++;
}
} else {
ret += dep[dx];
}
decode(T.substr(50, 36));
ret += dep[dy];
} else {
decode(T.substr(14, 36));
while (dx != dy) {
if (dep[dx] < dep[dy]) swap(dx, dy);
dx = par[dx];
ret++;
}
}
return ret;
}
Compilation message
Ali.cpp: In function 'void {anonymous}::dfs(int, int, int)':
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
Ali.cpp:36:3: note: in expansion of macro 'debug'
36 | debug(n);
| ^~~~~
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
Ali.cpp:46:4: note: in expansion of macro 'debug'
46 | debug("root", n, siz[n]);
| ^~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
Ali.cpp:108:2: note: in expansion of macro 'debug'
108 | debug("senda", bx, by);
| ^~~~~
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
Ali.cpp:121:2: note: in expansion of macro 'debug'
121 | debug(dis);
| ^~~~~
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
Ali.cpp:128:2: note: in expansion of macro 'debug'
128 | debug(ret);
| ^~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
10 | char _randmem[12379];
| ^~~~~~~~
Benjamin.cpp: In function 'std::string SendB(int, int, int)':
Benjamin.cpp:20:20: warning: statement has no effect [-Wunused-value]
20 | #define debug(...) 0
| ^
Benjamin.cpp:50:2: note: in expansion of macro 'debug'
50 | debug(bx, dx, by, dy);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1132 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1040 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1136 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1040 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 6 |
Correct |
8 ms |
1952 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1900 KB |
Output is correct |
| 8 |
Correct |
9 ms |
1908 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1904 KB |
Output is correct |
| 10 |
Correct |
7 ms |
2072 KB |
Output is correct |
| 11 |
Correct |
6 ms |
1680 KB |
Output is correct |
| 12 |
Correct |
9 ms |
1900 KB |
Output is correct |
| 13 |
Correct |
7 ms |
1904 KB |
Output is correct |
| 14 |
Correct |
5 ms |
2028 KB |
Output is correct |
| 15 |
Correct |
7 ms |
2700 KB |
Output is correct |
| 16 |
Correct |
7 ms |
2024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
1040 KB |
Output is partially correct |
| 2 |
Partially correct |
50 ms |
2632 KB |
Output is partially correct |
| 3 |
Partially correct |
3 ms |
1040 KB |
Output is partially correct |
| 4 |
Partially correct |
302 ms |
2008 KB |
Output is partially correct |
| 5 |
Partially correct |
223 ms |
2028 KB |
Output is partially correct |
| 6 |
Partially correct |
247 ms |
2032 KB |
Output is partially correct |
| 7 |
Partially correct |
239 ms |
2808 KB |
Output is partially correct |
| 8 |
Partially correct |
224 ms |
2012 KB |
Output is partially correct |
| 9 |
Partially correct |
223 ms |
2496 KB |
Output is partially correct |
| 10 |
Partially correct |
211 ms |
2864 KB |
Output is partially correct |
| 11 |
Partially correct |
208 ms |
1892 KB |
Output is partially correct |
| 12 |
Partially correct |
25 ms |
1832 KB |
Output is partially correct |
| 13 |
Partially correct |
129 ms |
1960 KB |
Output is partially correct |
| 14 |
Partially correct |
146 ms |
1924 KB |
Output is partially correct |
| 15 |
Partially correct |
6 ms |
1128 KB |
Output is partially correct |
| 16 |
Partially correct |
209 ms |
2808 KB |
Output is partially correct |
| 17 |
Partially correct |
241 ms |
2880 KB |
Output is partially correct |
| 18 |
Partially correct |
215 ms |
2484 KB |
Output is partially correct |
| 19 |
Partially correct |
198 ms |
2584 KB |
Output is partially correct |
| 20 |
Partially correct |
133 ms |
2324 KB |
Output is partially correct |
| 21 |
Partially correct |
184 ms |
2552 KB |
Output is partially correct |
| 22 |
Partially correct |
212 ms |
2028 KB |
Output is partially correct |
| 23 |
Partially correct |
190 ms |
1932 KB |
Output is partially correct |
| 24 |
Partially correct |
188 ms |
2020 KB |
Output is partially correct |
| 25 |
Partially correct |
196 ms |
2080 KB |
Output is partially correct |
| 26 |
Partially correct |
201 ms |
2016 KB |
Output is partially correct |
| 27 |
Partially correct |
196 ms |
2024 KB |
Output is partially correct |
| 28 |
Partially correct |
220 ms |
2008 KB |
Output is partially correct |
| 29 |
Partially correct |
195 ms |
1924 KB |
Output is partially correct |
| 30 |
Partially correct |
219 ms |
2060 KB |
Output is partially correct |
| 31 |
Partially correct |
201 ms |
2128 KB |
Output is partially correct |
| 32 |
Partially correct |
243 ms |
1992 KB |
Output is partially correct |
| 33 |
Partially correct |
259 ms |
1960 KB |
Output is partially correct |
| 34 |
Partially correct |
199 ms |
1928 KB |
Output is partially correct |
| 35 |
Partially correct |
215 ms |
1940 KB |
Output is partially correct |
| 36 |
Partially correct |
202 ms |
2092 KB |
Output is partially correct |
| 37 |
Partially correct |
192 ms |
1936 KB |
Output is partially correct |
| 38 |
Partially correct |
208 ms |
2012 KB |
Output is partially correct |
| 39 |
Partially correct |
33 ms |
2020 KB |
Output is partially correct |
| 40 |
Partially correct |
236 ms |
2680 KB |
Output is partially correct |
