| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 547859 |
2022-04-11T21:58:15 Z |
duality |
Flights (JOI22_flights) |
C++17 |
|
407 ms |
22996 KB |
#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}
// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
public:
template<typename T>
_Debug& operator,(T val) {
cout << val << endl;
return *this;
}
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif
// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back
// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;
// ---------- END OF TEMPLATE ----------
#include "Ali.h"
namespace {
#define B 7
int N;
vi adjList[20020],adjList2[20020];
int pre[20020],com[20020],c = 0,num = 0;
vi doDFS(int u,int p) {
vi vv;
vv.pb(u),pre[num++] = u;
for (int v: adjList[u]) {
if (v != p) {
vi vv2 = doDFS(v,u);
vv.insert(vv.end(),vv2.begin(),vv2.end());
}
}
if (vv.size() >= B) {
for (int v: vv) com[v] = c;
c++,vv.clear();
}
return vv;
}
int visited[20020],order[20020];
int siz[20020];
int doDFS2(int u,int p) {
vi l;
visited[u] = 1,siz[u] = 1;
for (int v: adjList2[u]) {
if (v != p) {
l.pb(doDFS2(v,u));
siz[u] += siz[v];
}
}
if (p == -1) {
int x = 0;
for (int v: adjList2[u]) {
if (v != p) {
int t = B-siz[v]-1;
while (t--) {
adjList[l[x]].pb(N);
adjList[N].pb(l[x]);
adjList2[l[x]].pb(N);
adjList2[N].pb(l[x]);
com[N] = com[l[x]],l[x] = N++,siz[u]++;
}
x++;
}
}
assert((siz[u] == B) || (siz[u] == 2*B-1));
if (siz[u] == B) {
int t = B-1;
while (t--) {
adjList[u].pb(N);
adjList[N].pb(u);
adjList2[u].pb(N);
adjList2[N].pb(u);
com[N] = com[u],u = N++;
}
}
return -1;
}
if (l.empty()) return u;
else return l[0];
}
string sub[20020];
string add(string s,int x) {
for (char &c: s) c += x;
return s;
}
int doDFS3(int u,int p) {
vector<string> vv;
sub[u] = "a";
for (int v: adjList2[u]) {
if (v != p) doDFS3(v,u),vv.pb(add(sub[v],1));
}
sort(vv.begin(),vv.end());
for (string s: vv) sub[u] += s;
return 0;
}
vi com2[20020];
int doDFS4(int u,int p,int c) {
order[u] = num++,com2[c].pb(u);
sort(adjList2[u].begin(),adjList2[u].end(),[](int a,int b) { return sub[a] < sub[b]; });
for (int v: adjList2[u]) {
if (v != p) doDFS4(v,u,c);
}
return 0;
}
int doDFS5(int u,int p,int e,int d) {
if (u == e) return d;
for (int v: adjList[u]) {
if (v != p) {
int x = doDFS5(v,u,e,d+1);
if (x != -1) return x;
}
}
return -1;
}
int getDist(int u,int v) {
return doDFS5(u,-1,v,0);
}
vpii all;
vector<vi> all2,all3,all4;
struct tree {
vpii edges;
string s;
int add(int x,int y) {
for (pii &p: edges) p.first += x,p.second += x;
for (char &c: s) c += y;
return 0;
}
};
vector<tree> trees[20];
vi adj[20];
int D[20][20];
int doDFS6(int u,int p,int r,int d) {
D[r][u] = d;
for (int v: adj[u]) {
if (v != p) doDFS6(v,u,r,d+1);
}
return 0;
}
int genTrees() {
int i,j;
for (i = 0; i <= 2*B-1; i++) trees[i].clear();
tree o;
o.s = "a";
trees[1].pb(o);
for (i = 2; i <= 2*B-1; i++) {
if (i-1 < B) {
for (tree t: trees[i-1]) {
tree t2 = t;
t2.add(1,1),t2.edges.pb(mp(0,1)),t2.s = "a" + t2.s;
trees[i].pb(t2);
}
}
for (j = 1; j <= i-2; j++) {
if ((j < B) && (i-j-1 < B)) {
for (tree t1: trees[j]) {
for (tree t2: trees[i-j-1]) {
if (t1.s <= t2.s) {
tree t3 = t1;
t3.add(1,1),t3.edges.pb(mp(0,1));
tree t4 = t2;
t4.add(j+1,1),t4.edges.pb(mp(0,j+1));
t3.edges.insert(t3.edges.end(),t4.edges.begin(),t4.edges.end());
t3.s = "a" + t3.s + t4.s;
trees[i].pb(t3);
}
}
}
}
}
}
for (tree t: trees[2*B-1]) {
for (i = 0; i < 2*B-1; i++) adj[i].clear();
for (pii p: t.edges) adj[p.first].pb(p.second),adj[p.second].pb(p.first);
for (i = 0; i < 2*B-1; i++) doDFS6(i,-1,i,0);
vi bfs;
for (i = 0; i < 2*B-1; i++) bfs.pb(i);
sort(bfs.begin(),bfs.end(),[&](int a,int b) { return mp(D[0][a],a) < mp(D[0][b],b); });
for (i = 0; i < 2*B-1; i++) {
assert(adj[i].size() <= 3);
if (adj[i].size() < 3) {
vi v;
for (j = 0; j < 2*B-1; j++) v.pb(D[i][bfs[j]]);
if (i == 0) all2.pb(v);
all3.pb(v);
}
}
vi v;
for (i = 0; i < 2*B-1; i++) {
for (j = i+1; j < 2*B-1; j++) v.pb(D[i][j]);
}
all4.pb(v);
}
sort(all2.begin(),all2.end());
all2.resize(unique(all2.begin(),all2.end())-all2.begin());
sort(all3.begin(),all3.end());
all3.resize(unique(all3.begin(),all3.end())-all3.begin());
sort(all4.begin(),all4.end());
all4.resize(unique(all4.begin(),all4.end())-all4.begin());
return 0;
}
}
void Init(int n,vector<int> U,vector<int> V) {
int i,j,o = n;
N = n;
for (i = 0; i < 2*N+20; i++) adjList[i].clear(),adjList2[i].clear();
for (i = 0; i < N-1; i++) adjList[U[i]].pb(V[i]),adjList[V[i]].pb(U[i]);
vi vv;
num = c = 0;
for (i = 0; i < N; i++) {
if (adjList[i].size() == 1) {
vv = doDFS(i,-1);
break;
}
}
if (!vv.empty()) {
swap(vv[0],vv.back());
while (vv.size() < B) {
adjList[vv.back()].pb(N);
adjList[N].pb(vv.back());
vv.pb(N),N++;
}
for (int v: vv) com[v] = c;
c++;
}
for (i = 0; i < N; i++) {
for (int v: adjList[i]) {
if (com[i] == com[v]) adjList2[i].pb(v);
}
}
fill(visited,visited+o,0);
for (i = 0; i < o; i++) {
if (!visited[pre[i]]) {
num = 0,com2[com[pre[i]]].clear();
doDFS2(pre[i],-1);
doDFS3(pre[i],-1);
doDFS4(pre[i],-1,com[pre[i]]);
sort(com2[com[pre[i]]].begin(),com2[com[pre[i]]].end(),[&](int a,int b) {
return mp(sub[pre[i]][order[a]],order[a]) < mp(sub[pre[i]][order[b]],order[b]);
});
for (j = 0; j < com2[com[pre[i]]].size(); j++) order[com2[com[pre[i]]][j]] = j;
}
}
for (i = 0; i < o; i++) SetID(i,(2*B-1)*com[i]+order[i]);
if (trees[2*B-1].empty()) {
for (i = 0; i < 1447; i++) {
for (j = i; j < 1447; j++) all.pb(mp(i,j));
}
genTrees();
}
}
string SendA(string S) {
int i,b = 0;
assert(S.size() == 20);
for (i = 0; i < S.size(); i++) {
if (S[i] == '1') b |= (1 << i);
}
int x = all[b].first,y = all[b].second;
vi comx = com2[x],comy = com2[y];
if (x == y) {
int j;
vi D;
for (i = 0; i < comx.size(); i++) {
for (j = i+1; j < comy.size(); j++) D.pb(getDist(comx[i],comy[j]));
}
LLI ret = lower_bound(all4.begin(),all4.end(),D)-all4.begin()+2;
string r;
while (ret > 0) r += '0'+(ret % 2),ret /= 2;
r.pop_back();
return r;
}
else {
assert(x < y);
int j,m = 1e9;
vector<vi> D(comx.size());
for (i = 0; i < comx.size(); i++) {
D[i].resize(comy.size());
for (j = 0; j < comy.size(); j++) D[i][j] = getDist(comx[i],comy[j]),m = min(m,D[i][j]);
}
for (i = 0; i < comx.size(); i++) {
for (j = 0; j < comy.size(); j++) {
if (D[i][j] == m) break;
}
if (j < comy.size()) break;
}
int xx = i,yy = j;
vi vx,vy;
for (i = 0; i < comx.size(); i++) vx.pb(D[i][yy]-m);
for (i = 0; i < comy.size(); i++) vy.pb(D[xx][i]-m);
int px = lower_bound(all2.begin(),all2.end(),vx)-all2.begin();
int py = lower_bound(all3.begin(),all3.end(),vy)-all3.begin();
LLI ret = (LLI) m*all2.size()*all3.size()+(LLI) px*all3.size()+py+2;
string r;
while (ret > 0) r += '0'+(ret % 2),ret /= 2;
r.pop_back();
return r;
}
}
#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}
// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
public:
template<typename T>
_Debug& operator,(T val) {
cout << val << endl;
return *this;
}
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif
// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back
// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;
// ---------- END OF TEMPLATE ----------
#include "Benjamin.h"
namespace {
#define B 7
int X,Y;
vpii all;
vector<vi> all2,all3,all4;
struct tree {
vpii edges;
string s;
int add(int x,int y) {
for (pii &p: edges) p.first += x,p.second += x;
for (char &c: s) c += y;
return 0;
}
};
vector<tree> trees[20];
vi adj[20];
int D[20][20];
int doDFS6(int u,int p,int r,int d) {
D[r][u] = d;
for (int v: adj[u]) {
if (v != p) doDFS6(v,u,r,d+1);
}
return 0;
}
int genTrees() {
int i,j;
for (i = 0; i <= 2*B-1; i++) trees[i].clear();
tree o;
o.s = "a";
trees[1].pb(o);
for (i = 2; i <= 2*B-1; i++) {
if (i-1 < B) {
for (tree t: trees[i-1]) {
tree t2 = t;
t2.add(1,1),t2.edges.pb(mp(0,1)),t2.s = "a" + t2.s;
trees[i].pb(t2);
}
}
for (j = 1; j <= i-2; j++) {
if ((j < B) && (i-j-1 < B)) {
for (tree t1: trees[j]) {
for (tree t2: trees[i-j-1]) {
if (t1.s <= t2.s) {
tree t3 = t1;
t3.add(1,1),t3.edges.pb(mp(0,1));
tree t4 = t2;
t4.add(j+1,1),t4.edges.pb(mp(0,j+1));
t3.edges.insert(t3.edges.end(),t4.edges.begin(),t4.edges.end());
t3.s = "a" + t3.s + t4.s;
trees[i].pb(t3);
}
}
}
}
}
}
for (tree t: trees[2*B-1]) {
for (i = 0; i < 2*B-1; i++) adj[i].clear();
for (pii p: t.edges) adj[p.first].pb(p.second),adj[p.second].pb(p.first);
for (i = 0; i < 2*B-1; i++) doDFS6(i,-1,i,0);
vi bfs;
for (i = 0; i < 2*B-1; i++) bfs.pb(i);
sort(bfs.begin(),bfs.end(),[&](int a,int b) { return mp(D[0][a],a) < mp(D[0][b],b); });
for (i = 0; i < 2*B-1; i++) {
assert(adj[i].size() <= 3);
if (adj[i].size() < 3) {
vi v;
for (j = 0; j < 2*B-1; j++) v.pb(D[i][bfs[j]]);
if (i == 0) all2.pb(v);
all3.pb(v);
}
}
vi v;
for (i = 0; i < 2*B-1; i++) {
for (j = i+1; j < 2*B-1; j++) v.pb(D[i][j]);
}
all4.pb(v);
}
sort(all2.begin(),all2.end());
all2.resize(unique(all2.begin(),all2.end())-all2.begin());
sort(all3.begin(),all3.end());
all3.resize(unique(all3.begin(),all3.end())-all3.begin());
sort(all4.begin(),all4.end());
all4.resize(unique(all4.begin(),all4.end())-all4.begin());
return 0;
}
}
string SendB(int N,int X,int Y) {
if (X > Y) swap(X,Y);
::X = X,::Y = Y;
int i,j;
if (trees[B].empty()) {
for (i = 0; i < 1447; i++) {
for (j = i; j < 1447; j++) all.pb(mp(i,j));
}
genTrees();
}
pii p = mp(X/(2*B-1),Y/(2*B-1));
int pos = lower_bound(all.begin(),all.end(),p)-all.begin();
string r;
for (i = 0; i < 20; i++) {
if (pos & (1 << i)) r += '1';
else r += '0';
}
return r;
}
int Answer(string T) {
T += '1';
int i,j;
LLI ret = 0;
for (i = 0; i < T.size(); i++) {
if (T[i] == '1') ret |= (1LL << i);
}
ret -= 2;
if (X/(2*B-1) == Y/(2*B-1)) {
int c = 0;
for (i = 0; i < 2*B-1; i++) {
for (j = i+1; j < 2*B-1; j++) {
if ((i == (X % (2*B-1))) && (j == (Y % (2*B-1)))) break;
else c++;
}
if (j < 2*B-1) break;
}
return all4[ret][c];
}
else {
int d = ret/all2.size()/all3.size();
int px = (ret/all3.size()) % all2.size();
int py = ret % all3.size();
return d + all2[px][X % (2*B-1)] + all3[py][Y % (2*B-1)];
}
}
Compilation message
Ali.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>)':
Ali.cpp:286:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
286 | for (j = 0; j < com2[com[pre[i]]].size(); j++) order[com2[com[pre[i]]][j]] = j;
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:301:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
301 | for (i = 0; i < S.size(); i++) {
| ~~^~~~~~~~~~
Ali.cpp:309:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
309 | for (i = 0; i < comx.size(); i++) {
| ~~^~~~~~~~~~~~~
Ali.cpp:310:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
310 | for (j = i+1; j < comy.size(); j++) D.pb(getDist(comx[i],comy[j]));
| ~~^~~~~~~~~~~~~
Ali.cpp:322:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
322 | for (i = 0; i < comx.size(); i++) {
| ~~^~~~~~~~~~~~~
Ali.cpp:324:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
324 | for (j = 0; j < comy.size(); j++) D[i][j] = getDist(comx[i],comy[j]),m = min(m,D[i][j]);
| ~~^~~~~~~~~~~~~
Ali.cpp:326:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
326 | for (i = 0; i < comx.size(); i++) {
| ~~^~~~~~~~~~~~~
Ali.cpp:327:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
327 | for (j = 0; j < comy.size(); j++) {
| ~~^~~~~~~~~~~~~
Ali.cpp:330:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
330 | if (j < comy.size()) break;
| ~~^~~~~~~~~~~~~
Ali.cpp:334:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
334 | for (i = 0; i < comx.size(); i++) vx.pb(D[i][yy]-m);
| ~~^~~~~~~~~~~~~
Ali.cpp:335:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
335 | for (i = 0; i < comy.size(); i++) vy.pb(D[xx][i]-m);
| ~~^~~~~~~~~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
10 | char _randmem[12379];
| ^~~~~~~~
Benjamin.cpp: In function 'int Answer(std::string)':
Benjamin.cpp:171:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for (i = 0; i < T.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
19304 KB |
Output is correct |
| 2 |
Correct |
35 ms |
19268 KB |
Output is correct |
| 3 |
Correct |
35 ms |
19264 KB |
Output is correct |
| 4 |
Correct |
33 ms |
19272 KB |
Output is correct |
| 5 |
Correct |
36 ms |
19356 KB |
Output is correct |
| 6 |
Correct |
85 ms |
20844 KB |
Output is correct |
| 7 |
Correct |
72 ms |
20716 KB |
Output is correct |
| 8 |
Correct |
51 ms |
20724 KB |
Output is correct |
| 9 |
Correct |
59 ms |
20760 KB |
Output is correct |
| 10 |
Correct |
98 ms |
21268 KB |
Output is correct |
| 11 |
Correct |
44 ms |
20828 KB |
Output is correct |
| 12 |
Correct |
46 ms |
20376 KB |
Output is correct |
| 13 |
Correct |
48 ms |
20356 KB |
Output is correct |
| 14 |
Correct |
53 ms |
21020 KB |
Output is correct |
| 15 |
Correct |
66 ms |
22516 KB |
Output is correct |
| 16 |
Correct |
48 ms |
20532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
19264 KB |
Output is correct |
| 2 |
Partially correct |
407 ms |
22996 KB |
Output is partially correct |
| 3 |
Incorrect |
18 ms |
10676 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
