oj.uz

답안 #1014173

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1014173 2024-07-04T13:30:15 Z Dzadzo 통행료 (IOI18_highway) C++17
0 / 100
 12 ms 11096 KB 
#include <bits/stdc++.h>
#include "highway.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF INT_MAX
#define MOD 1000000007
#define MAXN 200000
using namespace std;

/*
ll ask(vi arr) {
    for (int x:arr)cout<<x<<" ";
    cout<<'\n';
    ll res;
    cin>>res;
    return res;
}
void answer(int x,int y) {
    cout<<x<<" "<<y<<"\n";
}
*/

vi edges;
vvp adj(MAXN+1);
vvp depth(MAXN+1);


void dfs(int v,int p,int d) {
    for (auto &[to,id]:adj[v]) {
        if (to==p)continue;
        depth[d].pb({to,id});
        edges.pb(id);
        dfs(to,v,d+1);
    }
}
void find_pair(int n,vi U,vi V,int A,int B) {
    for (int i=0;i<n-1;i++) {
        adj[U[i]].pb({V[i],i});
        adj[V[i]].pb({U[i],i});
    }
    vi w(n-1);
    ll dist=ask(w);
    int res=-1;
    for (int bit=15;bit>=0;bit--) {
        if (res+(1<<bit)>=n-1)continue;
        for (int i=0;i<=res+(1<<bit);i++)w[i]=1;
        ll cur=ask(w);
        for (int i=0;i<=res+(1<<bit);i++)w[i]=0;
        if (cur==dist)res+=(1<<bit);

    }
    res++;
    cout<<V[res]<<" "<<U[res]<<'\n';

    depth[0].pb({V[res],res});

    dfs(V[res],U[res],1);
    for (int x:edges)w[x]=1;
    ll distx=( ask (w) - dist ) / ( B - A );
    for (int x:edges)w[x]=0;
    ll disty= dist/A - distx - 1;

    cout<<distx<<" "<<disty<<"\n";
    int idx=-1;
    for (int bit=15;bit>=0;bit--) {
        if ( idx+(1<<bit) >= depth[distx].size() )continue;
        for (int i=0;i<=idx+(1<<bit);i++)w[depth[distx][i].S]=1;
        ll cur=ask(w);
        for (int i=0;i<=idx+(1<<bit);i++)w[depth[distx][i].S]=0;
        if (cur == dist )idx+=(1<<bit);
    }
    idx=depth[distx][idx+1].F;

    depth.assign(MAXN+1,{});
    depth[0].pb({U[res],res});
    dfs(U[res],V[res],1);

    int idy=-1;
    for (int bit=15;bit>=0;bit--) {
        if ( idy+(1<<bit) >= depth[disty].size() )continue;
        for (int i=0;i<=idy+(1<<bit);i++)w[depth[disty][i].S]=1;
        ll cur=ask(w);
        for (int i=0;i<=idy+(1<<bit);i++)w[depth[disty][i].S]=0;
        if (cur == dist )idy+=(1<<bit);
    }
    idy=depth[disty][idy+1].F;


    answer(idx,idy);
}
/*
signed main() {
    int n;
    cin>>n;
    vi V,U;
    for (int i=0;i<n-1;i++) {
        int u,v;
        cin>>u>>v;
        V.pb(v);
        U.pb(u);
    }
    int A,B;
    cin>>A>>B;
    find_pair(n,U,V,A,B);
}
*/

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if ( idx+(1<<bit) >= depth[distx].size() )continue;
      |              ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
highway.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         if ( idy+(1<<bit) >= depth[disty].size() )continue;
      |              ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 9816 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 9816 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 11096 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 9816 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 10328 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 10328 KB Incorrect
2 Halted 0 ms 0 KB -