Submission #547861

#	Time	Username	Problem	Language	Result	Execution time	Memory
547861		duality	Flights (JOI22_flights)	C++17	97 / 100	2755 ms	23052 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

#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[bfs[i]][bfs[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[bfs[i]][bfs[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 (stderr)

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++) {
      |                 ~~^~~~~~~~~~

Subtask 115 / 15

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 282 / 85

#	Verdict	Execution time	Memory	Grader output
Fetching results...