oj.uz

답안 #897306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897306 2024-01-02T21:36:48 Z alexander707070 Flights (JOI22_flights) C++17
15 / 100
 353 ms 6176 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=n-1;i>=0;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[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: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}::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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2444 KB Output is correct
2 Correct 1 ms 2444 KB Output is correct
3 Correct 1 ms 2700 KB Output is correct
4 Correct 1 ms 2440 KB Output is correct
5 Correct 2 ms 2440 KB Output is correct
6 Correct 9 ms 3324 KB Output is correct
7 Correct 9 ms 3228 KB Output is correct
8 Correct 8 ms 3232 KB Output is correct
9 Correct 11 ms 3432 KB Output is correct
10 Correct 13 ms 3700 KB Output is correct
11 Correct 6 ms 3052 KB Output is correct
12 Correct 6 ms 3252 KB Output is correct
13 Correct 7 ms 3476 KB Output is correct
14 Correct 6 ms 3300 KB Output is correct
15 Correct 8 ms 4876 KB Output is correct
16 Correct 7 ms 3696 KB Output is correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 2456 KB Output is partially correct
2 Partially correct 67 ms 5120 KB Output is partially correct
3 Partially correct 3 ms 2460 KB Output is partially correct
4 Partially correct 353 ms 4416 KB Output is partially correct
5 Partially correct 320 ms 3772 KB Output is partially correct
6 Partially correct 335 ms 4068 KB Output is partially correct
7 Partially correct 322 ms 6176 KB Output is partially correct
8 Partially correct 339 ms 4128 KB Output is partially correct
9 Partially correct 220 ms 4360 KB Output is partially correct
10 Partially correct 229 ms 4476 KB Output is partially correct
11 Partially correct 275 ms 3780 KB Output is partially correct
12 Partially correct 29 ms 3352 KB Output is partially correct
13 Incorrect 1 ms 1868 KB Incorrect
14 Halted 0 ms 0 KB -