oj.uz

Submission #897314

# Submission time Handle Problem Language Result Execution time Memory
897314 2024-01-02T21:41:46 Z alexander707070 Flights (JOI22_flights) C++17
15 / 100
 369 ms 5308 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(8);
    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 2440 KB Output is correct
3 Correct 1 ms 2448 KB Output is correct
4 Correct 1 ms 2444 KB Output is correct
5 Correct 1 ms 2436 KB Output is correct
6 Correct 11 ms 3256 KB Output is correct
7 Correct 11 ms 3472 KB Output is correct
8 Correct 9 ms 3252 KB Output is correct
9 Correct 9 ms 3092 KB Output is correct
10 Correct 9 ms 3840 KB Output is correct
11 Correct 8 ms 3008 KB Output is correct
12 Correct 7 ms 3528 KB Output is correct
13 Correct 6 ms 3276 KB Output is correct
14 Correct 6 ms 3296 KB Output is correct
15 Correct 8 ms 4380 KB Output is correct
16 Correct 7 ms 3288 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2464 KB Output is partially correct
2 Partially correct 71 ms 5308 KB Output is partially correct
3 Partially correct 4 ms 2456 KB Output is partially correct
4 Partially correct 369 ms 4152 KB Output is partially correct
5 Partially correct 343 ms 4020 KB Output is partially correct
6 Partially correct 345 ms 4104 KB Output is partially correct
7 Partially correct 315 ms 4956 KB Output is partially correct
8 Partially correct 367 ms 4432 KB Output is partially correct
9 Partially correct 223 ms 4568 KB Output is partially correct
10 Partially correct 225 ms 5156 KB Output is partially correct
11 Partially correct 281 ms 3732 KB Output is partially correct
12 Partially correct 32 ms 3416 KB Output is partially correct
13 Partially correct 139 ms 3792 KB Output is partially correct
14 Partially correct 186 ms 3912 KB Output is partially correct
15 Partially correct 6 ms 2720 KB Output is partially correct
16 Partially correct 236 ms 4916 KB Output is partially correct
17 Partially correct 233 ms 5116 KB Output is partially correct
18 Partially correct 244 ms 5064 KB Output is partially correct
19 Incorrect 151 ms 4696 KB Incorrect
20 Halted 0 ms 0 KB -