Submission #547527

#	Time	Username	Problem	Language	Result	Execution time	Memory
547527		duality	Flights (JOI22_flights)	C++17	82 / 100	3540 ms	26540 KiB

Ali

#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 doDFS(int u,int p) {
    vi vv;
    vv.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) {
                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;
    }
    for (i = 2*B-1; i >= B; i--) {
        trees[i].clear();
        for (tree t: trees[i-1]) {
            tree t2 = t;
            t2.add(1);
            t2.edges.pb(mp(0,1));
            trees[i].pb(t2);
        }
    }
    //cout<<"here3"<<endl;
    for (i = B; 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++) {
                //if (adj[j].size() == 1) {
                    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;
    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) {
            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),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 (i = 0; i < N; i++) {
        if (!visited[i] && (adjList2[i].size() == 1)) {
            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]);
    int j;
    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()+1;
        //printVar(ret);
        string r;
        while (ret > 0) r += '0'+(ret % 2),ret /= 2;
        if (r.empty()) r = "0";
        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+1;
        string r;
        while (ret > 0) r += '0'+(ret % 2),ret /= 2;
        if (r.empty()) r = "0";
        return r;
    }
}

Benjamin

#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) {
                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 >= B; i--) {
        trees[i].clear();
        for (tree t: trees[i-1]) {
            tree t2 = t;
            t2.add(1);
            t2.edges.pb(mp(0,1));
            trees[i].pb(t2);
        }
    }
    for (i = B; 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++) {
                //if (adj[j].size() == 1) {
                    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;
    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) {
    //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--;
    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 (stderr)

Ali.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>)':
Ali.cpp:218:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |         for (i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:262:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  262 |     for (i = 0; i < S.size(); i++) {
      |                 ~~^~~~~~~~~~
Ali.cpp:270:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  270 |         for (i = 0; i < comx.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
Ali.cpp:271:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |             for (j = i+1; j < comy.size(); j++) D.pb(getDist(comx[i],comy[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: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 < comy.size(); j++) D[i][j] = getDist(comx[i],comy[j]),m = min(m,D[i][j]);
      |                         ~~^~~~~~~~~~~~~
Ali.cpp:288:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  288 |         for (i = 0; i < comx.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
Ali.cpp:289:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  289 |             for (j = 0; j < comy.size(); j++) {
      |                         ~~^~~~~~~~~~~~~
Ali.cpp:292:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  292 |             if (j < comy.size()) break;
      |                 ~~^~~~~~~~~~~~~
Ali.cpp:296:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  296 |         for (i = 0; i < comx.size(); i++) vx.pb(D[i][yy]-m);
      |                     ~~^~~~~~~~~~~~~
Ali.cpp:297:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  297 |         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:173:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |     for (i = 0; i < T.size(); i++) {
      |                 ~~^~~~~~~~~~
Benjamin.cpp:180:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  180 |             if (all3[ret].size() == i*(i-1)/2) break;
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 67 / 85