| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 547545 |
2022-04-10T22:47:52 Z |
duality |
Flights (JOI22_flights) |
C++17 |
|
61 ms |
18520 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[10010],adjList2[10010];
int com[10010],c = 0;
vi pre;
vi doDFS(int u,int p) {
vi vv;
vv.pb(u),pre.pb(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[10010],order[10010],num = 0,cc;
vi com2[10010];
int siz[10010];
int getSize(int u,int p) {
siz[u] = 1;
for (int v: adjList2[u]) {
if (v != p) getSize(v,u),siz[u] += siz[v];
}
return 0;
}
int doDFS2(int u,int p) {
visited[u] = 1,order[u] = num++,com2[cc].pb(u);
sort(adjList2[u].begin(),adjList2[u].end(),[](int a,int b) { return siz[a] < siz[b]; });
for (int v: adjList2[u]) {
if (v != p) doDFS2(v,u);
}
return 0;
}
int doDFS3(int u,int p,int e,int d) {
if (u == e) return d;
for (int v: adjList[u]) {
if (v != p) {
int x = doDFS3(v,u,e,d+1);
if (x != -1) return x;
}
}
return -1;
}
int getDist(int u,int v) {
return doDFS3(u,-1,v,0);
}
vpii all;
vector<vi> all2,all3;
struct tree {
vpii edges;
int add(int x) {
for (pii &p: edges) p.first += x,p.second += x;
return 0;
}
};
vector<tree> trees[20];
vi adj[20];
int D[20][20];
int doDFS4(int u,int p,int r,int d) {
D[r][u] = d;
for (int v: adj[u]) {
if (v != p) doDFS4(v,u,r,d+1);
}
return 0;
}
int genTrees() {
int i,j,k;
for (i = 0; i <= 2*B-1; i++) trees[i].clear();
tree o;
trees[1].pb(o);
for (i = 2; i <= 2*B-1; i++) {
for (tree t: trees[i-1]) {
tree t2 = t;
t2.add(1);
t2.edges.pb(mp(0,1));
trees[i].pb(t2);
}
for (j = 1; j <= i-2; j++) {
if ((j <= i-j-1) && (j < B) && (i-j-1 < B)) {
for (tree t1: trees[j]) {
for (tree t2: trees[i-j-1]) {
tree t3 = t1;
t3.add(1),t3.edges.pb(mp(0,1));
tree t4 = t2;
t4.add(j+1),t4.edges.pb(mp(0,j+1));
t3.edges.insert(t3.edges.end(),t4.edges.begin(),t4.edges.end());
trees[i].pb(t3);
}
}
}
}
//cout<<i<<":"<<trees[i].size()<<endl;
}
//cout<<"here3"<<endl;
for (i = 2*B-1; i <= 2*B-1; i++) {
//cout<<"i:"<<i<<endl;
for (tree t: trees[i]) {
for (j = 0; j < i; j++) adj[j].clear();
for (pii p: t.edges) {
adj[p.first].pb(p.second);
adj[p.second].pb(p.first);
}
for (j = 0; j < i; j++) doDFS4(j,-1,j,0);
for (j = 0; j < i; j++) {
assert(adj[j].size() <= 3);
if (adj[j].size() < 3) {
vi v;
for (k = 0; k < i; k++) v.pb(D[j][k]);
all2.pb(v);
}
}
vi v;
for (j = 0; j < i; j++) {
for (k = j+1; k < i; k++) v.pb(D[j][k]);
}
all3.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());
//cout<<all2.size()<<";"<<all3.size()<<endl;
return 0;
}
}
void Init(int N,vector<int> U,vector<int> V) {
int i,j;
int o = N;
::N = N;
for (i = 0; i < N+10; i++) adjList[i].clear(),adjList2[i].clear();
c = 0;
for (i = 0; i < N-1; i++) adjList[U[i]].pb(V[i]),adjList[V[i]].pb(U[i]);
vi vv;
int r;
for (i = 0; i < N; i++) {
if (adjList[i].size() == 1) {
pre.clear();
vv = doDFS(i,-1);
r = i;
break;
}
}
if (!vv.empty()) {
for (i = 0; i < vv.size(); i++) {
if (vv[i] == r) {
swap(vv[i],vv.back());
break;
}
}
while (vv.size() < B) {
adjList[vv.back()].pb(N);
adjList[N].pb(vv.back());
vv.pb(N),pre.pb(N),N++;
}
for (int v: vv) com[v] = c;
c++;
}
//printArr(com,N);
for (i = 0; i < N; i++) {
for (int v: adjList[i]) {
if (com[i] == com[v]) adjList2[i].pb(v);
}
}
fill(visited,visited+N,0);
for (j = 0; j < N; j++) {
i = pre[j];
if (!visited[i]) {
num = 0,cc = com[i];
com2[cc].clear();
getSize(i,-1);
doDFS2(i,-1);
}
}
for (i = 0; i < o; i++) SetID(i,(2*B-1)*com[i]+order[i]);
if (trees[B].empty()) {
all.clear();
for (i = 0; i < 1429; i++) {
for (j = i; j < 1429; j++) all.pb(mp(i,j));
}
all2.clear(),all3.clear();
//cout<<"here"<<endl;
genTrees();
//cout<<"here2"<<endl;
}
}
string SendA(string S) {
//cout<<"SendA " << S <<endl;
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]));
}
//printArr(D,D.size());
LLI ret = lower_bound(all3.begin(),all3.end(),D)-all3.begin()+5;
//printVar(ret);
string r;
while (ret > 0) r += '0'+(ret % 2),ret /= 2;
r.pop_back();
return r;
}
else {
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);
//printArr(vx,vx.size());
//printArr(vy,vy.size());
int px = lower_bound(all2.begin(),all2.end(),vx)-all2.begin();
int py = lower_bound(all2.begin(),all2.end(),vy)-all2.begin();
//printVar(px);
//printVar(py);
//printArr(all2[px],all2[px].size());
//printArr(all2[py],all2[py].size());
LLI ret = (LLI) m*all2.size()*all2.size()+(LLI) px*all2.size()+py+5;
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;
struct tree {
vpii edges;
int add(int x) {
for (pii &p: edges) p.first += x,p.second += x;
return 0;
}
};
vector<tree> trees[20];
vi adj[20];
int D[20][20];
int doDFS4(int u,int p,int r,int d) {
D[r][u] = d;
for (int v: adj[u]) {
if (v != p) doDFS4(v,u,r,d+1);
}
return 0;
}
int genTrees() {
int i,j,k;
for (i = 0; i <= 2*B-1; i++) trees[i].clear();
tree o;
trees[1].pb(o);
for (i = 2; i <= 2*B-1; i++) {
for (tree t: trees[i-1]) {
tree t2 = t;
t2.add(1);
t2.edges.pb(mp(0,1));
trees[i].pb(t2);
}
for (j = 1; j <= i-2; j++) {
if ((j <= i-j-1) && (j < B) && (i-j-1 < B)) {
for (tree t1: trees[j]) {
for (tree t2: trees[i-j-1]) {
tree t3 = t1;
t3.add(1),t3.edges.pb(mp(0,1));
tree t4 = t2;
t4.add(j+1),t4.edges.pb(mp(0,j+1));
t3.edges.insert(t3.edges.end(),t4.edges.begin(),t4.edges.end());
trees[i].pb(t3);
}
}
}
}
}
for (i = 2*B-1; i <= 2*B-1; i++) {
for (tree t: trees[i]) {
for (j = 0; j < i; j++) adj[j].clear();
for (pii p: t.edges) {
adj[p.first].pb(p.second);
adj[p.second].pb(p.first);
}
for (j = 0; j < i; j++) doDFS4(j,-1,j,0);
for (j = 0; j < i; j++) {
assert(adj[j].size() <= 3);
if (adj[j].size() < 3) {
vi v;
for (k = 0; k < i; k++) v.pb(D[j][k]);
all2.pb(v);
}
}
vi v;
for (j = 0; j < i; j++) {
for (k = j+1; k < i; k++) v.pb(D[j][k]);
}
all3.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());
//cout<<all2.size()<<";"<<all3.size()<<endl;
return 0;
}
}
string SendB(int N,int X,int Y) {
//cout<<"SendB "<<N<<" "<<X<<" "<<Y<<endl;
if (X > Y) swap(X,Y);
::X = X,::Y = Y;
int i,j;
if (trees[B].empty()) {
all.clear();
for (i = 0; i < 1429; i++) {
for (j = i; j < 1429; j++) all.pb(mp(i,j));
}
all2.clear(),all3.clear();
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';
//cout<<"Answer "<<T<<endl;
int i,j;
LLI ret = 0;
for (i = 0; i < T.size(); i++) {
if (T[i] == '1') ret |= (1LL << i);
}
ret -= 5;
if (X/(2*B-1) == Y/(2*B-1)) {
//cout<<"siz:"<<all3[ret].size()<<endl;
for (i = B; i <= 2*B-1; i++) {
if (all3[ret].size() == i*(i-1)/2) break;
}
int s = i,c = 0;
//cout<<"s:"<<i<<endl;
for (i = 0; i < s; i++) {
for (j = i+1; j < s; j++) {
if ((i == (X % (2*B-1))) && (j == (Y % (2*B-1)))) break;
else c++;
}
if (j < s) break;
}
//cout<<"c:"<<c<<endl;
return all3[ret][c];
}
else {
int d = ret/all2.size()/all2.size();
int px = (ret/all2.size()) % all2.size();
int py = ret % all2.size();
//cout<<d<<";;"<<px<<";;"<<py<<endl;
//for (int k: all2[px])cout<<k<<" ";
//cout<<endl;
//for (int k: all2[py])cout<<k<<" ";
//cout<<endl;
return d + all2[px][X % (2*B-1)] + all2[py][Y % (2*B-1)];
}
}
Compilation message
Ali.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>)':
Ali.cpp:212:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
212 | for (i = 0; i < vv.size(); i++) {
| ~~^~~~~~~~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:258:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
258 | for (i = 0; i < S.size(); i++) {
| ~~^~~~~~~~~~
Ali.cpp:266:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
266 | for (i = 0; i < comx.size(); i++) {
| ~~^~~~~~~~~~~~~
Ali.cpp:267:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
267 | for (j = i+1; j < comy.size(); j++) D.pb(getDist(comx[i],comy[j]));
| ~~^~~~~~~~~~~~~
Ali.cpp:280:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
280 | for (i = 0; i < comx.size(); i++) {
| ~~^~~~~~~~~~~~~
Ali.cpp:282:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
282 | for (j = 0; j < comy.size(); j++) D[i][j] = getDist(comx[i],comy[j]),m = min(m,D[i][j]);
| ~~^~~~~~~~~~~~~
Ali.cpp:284:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
284 | for (i = 0; i < comx.size(); i++) {
| ~~^~~~~~~~~~~~~
Ali.cpp:285:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
285 | for (j = 0; j < comy.size(); j++) {
| ~~^~~~~~~~~~~~~
Ali.cpp:288:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
288 | if (j < comy.size()) break;
| ~~^~~~~~~~~~~~~
Ali.cpp:292:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
292 | for (i = 0; i < comx.size(); i++) vx.pb(D[i][yy]-m);
| ~~^~~~~~~~~~~~~
Ali.cpp:293:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
293 | 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:168:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for (i = 0; i < T.size(); i++) {
| ~~^~~~~~~~~~
Benjamin.cpp:175:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
175 | if (all3[ret].size() == i*(i-1)/2) break;
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
18516 KB |
Output is correct |
| 2 |
Correct |
39 ms |
18456 KB |
Output is correct |
| 3 |
Correct |
40 ms |
18480 KB |
Output is correct |
| 4 |
Correct |
39 ms |
18384 KB |
Output is correct |
| 5 |
Correct |
39 ms |
18440 KB |
Output is correct |
| 6 |
Incorrect |
32 ms |
10560 KB |
Incorrect |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
18520 KB |
Output is correct |
| 2 |
Incorrect |
61 ms |
10648 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
