oj.uz

답안 #897286

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897286 2024-01-02T21:02:40 Z alexander707070 Flights (JOI22_flights) C++17
15 / 100
 358 ms 5152 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);
        }
    }
}

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

    reset();

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

    for(int i=0;i<n;i++){
        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[30],treer[30];
    int dst[30],as,bs;

    const int del=19;

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

    void dfs4(int x){
        while(true){
            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:127:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         if(i<code[xx].size())res.push_back(code[xx][i]+'0');
      |            ~^~~~~~~~~~~~~~~~
Ali.cpp:137:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         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}::dfs5(int)':
Benjamin.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         while(pt<coder.size()){
      |               ~~^~~~~~~~~~~~~
Benjamin.cpp: In function 'void {anonymous}::dfs6(int, int, int)':
Benjamin.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i=0;i<treel[x].size();i++){
      |                     ~^~~~~~~~~~~~~~~~
Benjamin.cpp: In function 'void {anonymous}::dfs7(int, int, int)':
Benjamin.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2288 KB Output is correct
2 Correct 1 ms 2440 KB Output is correct
3 Correct 1 ms 2444 KB Output is correct
4 Correct 1 ms 2444 KB Output is correct
5 Correct 1 ms 2444 KB Output is correct
6 Correct 9 ms 3232 KB Output is correct
7 Correct 8 ms 3324 KB Output is correct
8 Correct 9 ms 3224 KB Output is correct
9 Correct 12 ms 3072 KB Output is correct
10 Correct 10 ms 3992 KB Output is correct
11 Correct 7 ms 3056 KB Output is correct
12 Correct 6 ms 3228 KB Output is correct
13 Correct 7 ms 3460 KB Output is correct
14 Correct 6 ms 3272 KB Output is correct
15 Correct 7 ms 4804 KB Output is correct
16 Correct 7 ms 3252 KB Output is correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 2716 KB Output is partially correct
2 Partially correct 63 ms 5152 KB Output is partially correct
3 Partially correct 3 ms 2456 KB Output is partially correct
4 Partially correct 358 ms 3776 KB Output is partially correct
5 Failed 62 ms 3096 KB Unexpected end of file - int32 expected (Bruno)
6 Halted 0 ms 0 KB -