oj.uz

Submission #897310

# Submission time Handle Problem Language Result Execution time Memory
897310 2024-01-02T21:39:55 Z alexander707070 Flights (JOI22_flights) C++17
15 / 100
 353 ms 5520 KB 
#include<bits/stdc++.h>
#include "Ali.h"

#define MAXN 20007
using namespace std;

namespace{

    int n,xx,yy,k,root;
    const int bucket=10;

    vector<int> v[MAXN];

    int dist[MAXN],where[MAXN],num[MAXN],cnt[MAXN];
    int l,r,mins,currdist;
    vector<int> code[MAXN],nodes[MAXN];

    void reset(){
        k=0; mins=n+1;
        for(int i=0;i<n;i++){
            v[i].clear(); code[i].clear();
            nodes[i].clear();
            cnt[i]=0;
        }
    }

    vector<int> dfs(int x,int p){
        vector<int> comp={x},curr;

        for(int i=0;i<v[x].size();i++){
            if(v[x][i]==p)continue;
            curr=dfs(v[x][i],x);
            for(int f:curr)comp.push_back(f);
        }

        if(comp.size()>=bucket or p==-1){
            for(int f:comp)where[f]=k;
            nodes[k]=comp;

            k++; comp.clear();
        }

        return comp;
    }

    void dfs2(int x,int p){
        num[x]=where[x]*(2*bucket-1)+cnt[where[x]];
        SetID(x,num[x]); cnt[where[x]]++;

        for(int i=0;i<v[x].size();i++){
            if(v[x][i]==p)continue;

            if(where[x]==where[v[x][i]]){
                code[where[x]].push_back(0);
            }
            dfs2(v[x][i],x);
        }

        if(p!=-1 and where[x]==where[p]){
            code[where[x]].push_back(1);
        }       
    }

    void dfs3(int x,int p,int d){
        dist[x]=d;

        for(int i=0;i<v[x].size();i++){
            if(v[x][i]==p)continue;
            dfs3(v[x][i],x,d+1);
        }
    }
}

vector<int> perm;

void Init(int N, vector<int> U, vector<int> V){
    srand(7);
    n=N;

    reset();
    perm={};
    for(int i=0;i<n;i++)perm.push_back(i);

    for(int i=0;i<n-1;i++){
        v[U[i]].push_back(V[i]);
        v[V[i]].push_back(U[i]);
    }

    random_shuffle(perm.begin(),perm.end());

    for(int i:perm){
        if(v[i].size()<3)root=i;
    }

    dfs(root,-1);
    dfs2(root,-1);
}

string SendA(string S){
    xx=yy=0;

    for(int i=0;i<10;i++){
        xx*=2;
        if(S[i]=='1')xx++;
    }

    for(int i=0;i<10;i++){
        yy*=2;
        if(S[10+i]=='1')yy++;
    }

    for(int i:nodes[xx]){
        dfs3(i,-1,0);
        currdist=n;

        for(int f:nodes[yy]){
            currdist=min(currdist,dist[f]);
        }

        if(currdist<mins){
            mins=currdist;
            l=i;
            for(int f:nodes[yy]){
                if(dist[f]==mins)r=f;
            }
        }
    }

    l=num[l]%(2*bucket-1); r=num[r]%(2*bucket-1);

    string res="";
    
    for(int i=0;i<36;i++){
        if(i<code[xx].size())res.push_back(code[xx][i]+'0');
        else res+="1";
    }

    for(int i=3;i>=0;i--){
        if(((1<<i)&l)==0)res.push_back('0');
        else res.push_back('1');
    }

    for(int i=0;i<36;i++){
        if(i<code[yy].size())res.push_back(code[yy][i]+'0');
        else res.push_back('1');
    }

    for(int i=3;i>=0;i--){
        if(((1<<i)&r)==0)res.push_back('0');
        else res.push_back('1');
    }

    for(int i=13;i>=0;i--){
        if(((1<<i)&mins)==0)res.push_back('0');
        else res.push_back('1');
    }

    return res;
}
#include<bits/stdc++.h>
#include "Benjamin.h"

#define MAXN 20007
using namespace std;

namespace{
    int nn,from,to,s,pos,dis,ld,rd,pt,nd;
    vector<int> codel,coder;

    vector<int> treel[40],treer[40];
    int dst[40],as,bs;

    const int del=19;

    void resets(){
        codel.clear(); coder.clear();
        for(int i=0;i<40;i++){
            treel[i].clear();
            treer[i].clear();
            dst[i]=0;
        }
    }

    void dfs4(int x){
        while(pt<codel.size()){
            if(codel[pt]==0){
                nd++; pt++;
                treel[x].push_back(nd);
                treel[nd].push_back(x);

                dfs4(nd);
            }else{
                pt++;
                return;
            }
        }
    }

    void dfs5(int x){
        while(pt<coder.size()){
            if(coder[pt]==0){
                nd++; pt++;
                treer[x].push_back(nd);
                treer[nd].push_back(x);

                dfs5(nd);
            }else{
                pt++;
                return;
            }
        }
    }

    void dfs6(int x,int p,int d){
        dst[x]=d;
        for(int i=0;i<treel[x].size();i++){
            if(treel[x][i]==p)continue;
            dfs6(treel[x][i],x,d+1);
        }
    }

    void dfs7(int x,int p,int d){
        dst[x]=d;
        for(int i=0;i<treer[x].size();i++){
            if(treer[x][i]==p)continue;
            dfs7(treer[x][i],x,d+1);
        }
    }
}

string SendB(int N, int X, int Y){
    resets();
    
    nn=N; from=X; to=Y;
    if(from>to)swap(from,to);

    string res="";
    for(int i=9;i>=0;i--){
        if(((from/del)&(1<<i))==0)res.push_back('0');
        else res.push_back('1');
    }

    for(int i=9;i>=0;i--){
        if(((to/del)&(1<<i))==0)res.push_back('0');
        else res.push_back('1');
    }

    return res;
}

int Answer(string T){

    pos=ld=rd=0;
    
    for(int i=pos;i<pos+36;i++){
        codel.push_back(T[i]-'0');
    }
    pos+=36;

    for(int i=pos;i<pos+4;i++){
        ld*=2;
        if(T[i]=='1')ld++;
    }
    pos+=4;

    nd=pt=0;
    dfs4(0);

    if(from/del==to/del){
        dfs6(from%del,-1,0);
        return dst[to%del];
    }

    dfs6(ld,-1,0);
    as=dst[from%del];

    for(int i=pos;i<pos+36;i++){
        coder.push_back(T[i]-'0');
    }
    pos+=36;

    for(int i=pos;i<pos+4;i++){
        rd*=2;
        if(T[i]=='1')rd++;
    }
    pos+=4;

    nd=pt=0;
    dfs5(0);
    dfs7(rd,-1,0);

    bs=dst[to%del];

    dis=0;
    for(int i=pos;i<pos+14;i++){
        dis*=2;
        if(T[i]=='1')dis++;
    }

    return as+dis+bs;
}

Compilation message

Ali.cpp: In function 'std::vector<int> {anonymous}::dfs(int, int)':
Ali.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int i=0;i<v[x].size();i++){
      |                     ~^~~~~~~~~~~~
Ali.cpp: In function 'void {anonymous}::dfs2(int, int)':
Ali.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int i=0;i<v[x].size();i++){
      |                     ~^~~~~~~~~~~~
Ali.cpp: In function 'void {anonymous}::dfs3(int, int, int)':
Ali.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i=0;i<v[x].size();i++){
      |                     ~^~~~~~~~~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:134:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         if(i<code[xx].size())res.push_back(code[xx][i]+'0');
      |            ~^~~~~~~~~~~~~~~~
Ali.cpp:144:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         if(i<code[yy].size())res.push_back(code[yy][i]+'0');
      |            ~^~~~~~~~~~~~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'void {anonymous}::dfs4(int)':
Benjamin.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         while(pt<codel.size()){
      |               ~~^~~~~~~~~~~~~
Benjamin.cpp: In function 'void {anonymous}::dfs5(int)':
Benjamin.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         while(pt<coder.size()){
      |               ~~^~~~~~~~~~~~~
Benjamin.cpp: In function 'void {anonymous}::dfs6(int, int, int)':
Benjamin.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int i=0;i<treel[x].size();i++){
      |                     ~^~~~~~~~~~~~~~~~
Benjamin.cpp: In function 'void {anonymous}::dfs7(int, int, int)':
Benjamin.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i=0;i<treer[x].size();i++){
      |                     ~^~~~~~~~~~~~~~~~
Benjamin.cpp: At global scope:
Benjamin.cpp:8:20: warning: '{anonymous}::s' defined but not used [-Wunused-variable]
    8 |     int nn,from,to,s,pos,dis,ld,rd,pt,nd;
      |                    ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2436 KB Output is correct
2 Correct 1 ms 2656 KB Output is correct
3 Correct 1 ms 2440 KB Output is correct
4 Correct 1 ms 2268 KB Output is correct
5 Correct 1 ms 2440 KB Output is correct
6 Correct 9 ms 3332 KB Output is correct
7 Correct 9 ms 3100 KB Output is correct
8 Correct 9 ms 3356 KB Output is correct
9 Correct 9 ms 3272 KB Output is correct
10 Correct 9 ms 3800 KB Output is correct
11 Correct 6 ms 3084 KB Output is correct
12 Correct 8 ms 3256 KB Output is correct
13 Correct 6 ms 3264 KB Output is correct
14 Correct 6 ms 3304 KB Output is correct
15 Correct 7 ms 4020 KB Output is correct
16 Correct 8 ms 3480 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2448 KB Output is partially correct
2 Partially correct 69 ms 4848 KB Output is partially correct
3 Partially correct 3 ms 2712 KB Output is partially correct
4 Partially correct 351 ms 4404 KB Output is partially correct
5 Partially correct 331 ms 4004 KB Output is partially correct
6 Partially correct 353 ms 4196 KB Output is partially correct
7 Partially correct 310 ms 4744 KB Output is partially correct
8 Partially correct 347 ms 4444 KB Output is partially correct
9 Partially correct 225 ms 4560 KB Output is partially correct
10 Partially correct 247 ms 5520 KB Output is partially correct
11 Partially correct 287 ms 4044 KB Output is partially correct
12 Partially correct 29 ms 3552 KB Output is partially correct
13 Partially correct 140 ms 4040 KB Output is partially correct
14 Incorrect 73 ms 3080 KB Incorrect
15 Halted 0 ms 0 KB -