Submission #635864

#	Time	Username	Problem	Language	Result	Execution time	Memory
635864		Mahdi	Flights (JOI22_flights)	C++17	0 / 100	10 ms	2500 KiB

Ali

#include<bits/stdc++.h>
#include "Ali.h"
using namespace std;

namespace{
    const int M=1e4+5;
    int n, p[M], sz[M], rt, st[M];
    vector<int>g[M];
    string t[M];

    string eq(int v){
        string res="";
        v=st[v];
        for(int i=0;i<15;++i){
            if(v&1)
                res+="1";
            else
                res+="0";
            v>>=1;
        }
        return res;
    }

    void dfs(int &tm, const int &v, const int &pp=-1){
        st[v]=tm++;
        sz[v]=1;
        int x=-1, y=-1;
        for(int u: g[v]){
            if(u!=pp){
                dfs(tm, u, v);
                sz[v]+=sz[u];
                x=u;
            }
        }
        for(int u: g[v]){
            if(u!=pp && u!=x)
                y=u;
        }
        string tt=eq(v);
        if(x==-1)
            t[v]=tt;
        else if(y==-1){
            p[v]=p[x];
            t[p[x]]+=tt;
        }
        else{
            if(sz[x]<sz[y])
                swap(x, y);
            p[v]=p[x];
            t[p[x]]+=tt+t[p[y]];
        }
    }

    void dfs(){
        rt=0;
        while(g[rt].size()>2)
            ++rt;
        iota(p, p+n, 0);
        int tim=0;
        dfs(tim, rt);
    }
}

void Init(int N, vector<int> U, vector<int> V){
    n=N;
    for(int i=0;i<n;++i)
        g[i].clear();
    for(int i=0;i<n;++i)
        t[i]="";
    for(int i=0;i<n-1;++i){
        int u=U[i], v=V[i];
        g[u].push_back(v);
        g[v].push_back(u);
    }    
    dfs();
    for(int i=0;i<n;++i)
        SetID(i, st[i]);
}

string SendA(string S){
    return t[p[rt]];          
}

Benjamin

#include<bits/stdc++.h>
#include "Benjamin.h"
using namespace std;

namespace{
    const int M=1e4+5;
    int n, x, y, sz, a[M], mn[4*M], dis[M];
    vector<int>g[M];

    int min(int x, int lx, int rx, int l, int r){
        if(lx>=r || rx<=l)
            return n;
        if(lx>=l && rx<=r)
            return mn[x];
        int m=(lx+rx)/2;
        int L=min(2*x+1, lx, m, l, r), R=min(2*x+2, m, rx, l, r);
        if(a[L]<a[R])
            return L;
        return R;
    }

    int tab(int l, int r){
        if(l==r)
            return -1;
        int v=min(0, 0, sz, l, r);
        //cout<<l<<", "<<r<<" : "<<v<<'\n';
        int u=tab(l, v), w=tab(v+1, r);
        v=a[v];
        if(u!=-1){
            g[u].push_back(v);
            g[v].push_back(u);
        }
        if(w!=-1){
            g[w].push_back(v);
            g[v].push_back(w);
        }
        return v;
    }

    void bfs(const int &v, const int &p=-1){
        for(int u: g[v]){
            if(u!=p){
                dis[u]=dis[v]+1;
                bfs(u, v);
            }
        }
    }

}

string SendB(int N, int X, int Y) {
    n=N;
    x=X;
    y=Y;
    for(int i=0;i<n;++i)
        g[i].clear();
    return "00000000000000000000";
}

int Answer(string T) {
    for(int i=0;i<n;++i){
        int h=1;
        a[i]=0;
        for(int j=i*15;j<i*15+15;++j){
            if(T[j]=='1')
                a[i]+=h;
            h<<=1;
        }
    }
    //for(int i=0;i<n;++i)
    //    cout<<a[i]<<' ';
    //cout<<'\n';
    a[n]=1e9;
    sz=1;
    while(sz<n)
        sz<<=1;
    for(int i=0;i<n;++i)
        mn[i+sz-1]=i;
    for(int i=sz-2;i>=0;--i){
        if(a[mn[2*i+1]]<a[mn[2*i+2]])
            mn[i]=mn[2*i+1];
        else
            mn[i]=mn[2*i+2];
    }
    tab(0, n);
    dis[x]=0;
    bfs(x);
    return dis[y];
}

Compilation message (stderr)

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

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