Submission #1026030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026030		Unforgettablepl	Flights (JOI22_flights)	C++17	68 / 100	321 ms	3472 KiB

Ali

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

const int THRESHOLD = 7;
const int BLOCKS = 1430;
const int BLOCKSIZE = 13;

namespace {

vector<vector<int>> adj;
vector<int> subsize;
vector<int> root;
vector<int> depth;
vector<int> whichblock;
vector<int> whichinter;
vector<int> p;
int n;

}

void Init(int N, vector<int> U, vector<int> V) {
    adj = vector<vector<int>>(N);
    n = N;
    for(int i=0;i<n-1;i++){
        adj[U[i]].emplace_back(V[i]);
        adj[V[i]].emplace_back(U[i]);
    }
    vector<int> indegree(N);
    p = vector<int>(N);
    depth = vector<int>(N);
    whichblock = vector<int>(N);
    whichinter = vector<int>(N);
    function<void(int,int)> dfs = [&](int x,int dep){
        depth[x]=dep;
        for(int&i:adj[x])if(i!=p[x]){
            p[i]=x;indegree[x]++;
            dfs(i,dep+1);
        }
    };
    int roott;
    for(int i=0;i<N;i++)if(adj[i].size()<3){
        p[i]=-1;
        roott = i;
        dfs(i,1);
        break;
    }
    queue<int> q;
    subsize = vector<int>(N);
    for(int i=0;i<N;i++)if(indegree[i]==0)q.emplace(i);
    while(!q.empty()){
        auto curr = q.front();q.pop();
        subsize[curr] = 1;
        for(int&i:adj[curr])if(i!=p[curr] and subsize[i]<THRESHOLD)subsize[curr]+=subsize[i];
        if(p[curr]==-1)continue;
        if(--indegree[p[curr]]==0)q.emplace(p[curr]);
    }
    root = vector<int>();
    int blocks = 0;
    subsize[roott]=THRESHOLD;
    function<int(int,int,int)> numdfs = [&](int x,int blockid,int interid){
        if(THRESHOLD<=subsize[x]){
            blockid = blocks++;
            interid = 0;
            root.emplace_back(x);
        }
        SetID(x,blockid*BLOCKSIZE+interid);
        whichblock[x] = blockid;
        whichinter[x] = interid;
        int allocated = 1;
        for(int&i:adj[x])if(i!=p[x]){
            allocated += numdfs(i,blockid,interid+allocated);
        }
        if(THRESHOLD<=subsize[x])return 0;
        else return allocated;
    };
    numdfs(roott,-1,-1);
}

string SendA(string S) {
    int rex = 0;
    for(int bit=0;bit<20;bit++)if(S[bit]=='1')rex|=(1<<bit);
    int curr = 0;
    int A,B;
    for(int l=0;l<BLOCKS;l++){
        for(int r=l;r<BLOCKS;r++){
            if(curr++==rex){A=l;B=r;}
        }
    }
    string res;
    int interid;
    function<void(int)> senddfs = [&](int x){
        if(interid==BLOCKSIZE-1)return;
        for(int i=0;i<adj[x].size();i++)if(adj[x][i]==p[x])adj[x].erase(adj[x].begin()+i);
        if(adj[x].empty() or subsize[adj[x][0]]>=THRESHOLD)res.insert(res.end(),'0');
        else {
            res.insert(res.end(),'1');
            interid++;
            senddfs(adj[x][0]);
        }
        if(adj[x].size()<2 or subsize[adj[x][1]]>=THRESHOLD)res.insert(res.end(),'0');
        else {
            res.insert(res.end(),'1');
            interid++;
            senddfs(adj[x][1]);
        }
    };
    if(depth[root[A]]>depth[root[B]]){
        res.insert(res.end(),'1');
        swap(A,B);
    } else res.insert(res.end(),'0');
    int rooter = 0;
    int tempB = root[B];
    while(tempB!=-1 and whichblock[tempB]!=A)tempB=p[tempB];
    if(tempB!=-1)rooter = whichinter[tempB];
    for(int bit=0;bit<4;bit++)if(rooter&(1<<bit))res.insert(res.end(),'1');
                              else res.insert(res.end(),'0');
    {
        int tar;
        if(tempB==-1)tar = root[A];
        else tar = tempB;
        function<int(int,int)> dfs = [&](int x,int p){
            if(tar==x)return 0;
            int ans = 1e5;
            for(int&i:adj[x])if(i!=p)ans=min(ans,dfs(i,x)+1);
            return ans;
        };
        int ans = dfs(root[B],-1);
        for(int bit=0;bit<14;bit++)if(ans&(1<<bit))res.insert(res.end(),'1');
                                  else res.insert(res.end(),'0');
    }
    interid = 0;
    senddfs(root[A]);
    interid = 0;
    senddfs(root[B]);
    return res;
}

Benjamin

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

const int THRESHOLD = 7;
const int BLOCKS = 1430;
const int BLOCKSIZE = 13;

namespace {
int x,y;
}

string SendB(int N, int X, int Y) {
    if(X>Y)swap(X,Y);
    ::x = X;
    ::y = Y;
    X/=BLOCKSIZE;
    Y/=BLOCKSIZE;
    int ans;
    int curr = 0;
    for(int l=0;l<BLOCKS;l++){
        for(int r=l;r<BLOCKS;r++){
            if(l==X and r==Y)ans = curr;
            curr++;
        }
    }
    string res;
    for(int bit=0;bit<20;bit++)if(ans&(1<<bit))res.insert(res.end(),'1');
                               else res.insert(res.end(),'0');
    return res;
}

int Answer(string T) {
    int ptrused = 0;
    auto read = [&]{
        return T[ptrused++]=='1';
    };
    if(read())swap(x,y);
    int rooter = 0;
    for(int bit=0;bit<4;bit++)if(read())rooter|=(1<<bit);    
    int maindist = 0;
    for(int bit=0;bit<14;bit++)if(read())maindist|=(1<<bit);    
    int blockX = x/BLOCKSIZE;
    int blockY = y/BLOCKSIZE;
    vector<vector<int>> adj1(BLOCKSIZE);
    vector<vector<int>> adj2(BLOCKSIZE);
    int alloc;
    function<void(int,vector<vector<int>>&)> readdfs = [&](int x,vector<vector<int>> &adj){
        if(x==BLOCKSIZE-1)return;
        if(read()){
            adj[x].emplace_back(++alloc);
            adj[alloc].emplace_back(x);
            readdfs(alloc,adj);
        }
        if(read()){
            adj[x].emplace_back(++alloc);
            adj[alloc].emplace_back(x);
            readdfs(alloc,adj);
        }
    };
    alloc = 0;
    readdfs(0,adj1);
    alloc = 0;
    readdfs(0,adj2);
    if(blockX==blockY){
        int tar = y%BLOCKSIZE;
        function<int(int,int)> dfs = [&](int x,int p){
            if(tar==x)return 0;
            int ans = 1e5;
            for(int&i:adj1[x])if(i!=p)ans=min(ans,dfs(i,x)+1);
            return ans;
        };
        return dfs(x%BLOCKSIZE,-1);
    }
    vector<int> dist1(BLOCKSIZE);
    vector<int> dist2(BLOCKSIZE);
    function<void(int,int,int,vector<vector<int>>&,vector<int>&)> depthdfs = [&](int x,int p,int depth,vector<vector<int>> &adj,vector<int> &dist){
        dist[x] = depth;
        for(int&i:adj[x])if(i!=p)depthdfs(i,x,depth+1,adj,dist);
    };
    depthdfs(rooter,-1,0,adj1,dist1);
    depthdfs(0,-1,0,adj2,dist2);
    return dist1[x%BLOCKSIZE]+dist2[y%BLOCKSIZE]+maindist;
}

Compilation message (stderr)

Ali.cpp: In lambda function:
Ali.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int i=0;i<adj[x].size();i++)if(adj[x][i]==p[x])adj[x].erase(adj[x].begin()+i);
      |                     ~^~~~~~~~~~~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:108:35: warning: 'B' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |     if(depth[root[A]]>depth[root[B]]){
      |                                   ^
Ali.cpp:108:20: warning: 'A' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |     if(depth[root[A]]>depth[root[B]]){
      |                    ^
Ali.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>)':
Ali.cpp:60:18: warning: 'roott' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     subsize[roott]=THRESHOLD;
      |                  ^
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'std::string SendB(int, int, int)':
Benjamin.cpp:28:38: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |     for(int bit=0;bit<20;bit++)if(ans&(1<<bit))res.insert(res.end(),'1');
      |                                   ~~~^~~~~~~~~

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