oj.uz

답안 #114037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114037 2019-05-29T17:11:59 Z thebes 통행료 (IOI18_highway) C++14
6 / 100
 790 ms 32208 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
const int MN = 9e4+4, MM = 1.3e5+5;
ll m, st, lo, hi, mm, i, x, y, vis[MN], s, t, d[MN], u[MN]; vector<int> q;
map<pair<ll,ll>,ll> id;
vector<ll> adj[MN], tr[MN], ls;
queue<ll> qq;
void sett(ll l){
    for(int i=0;i<q.size();i++)
        q[i]=(i<=l);
}
void dfs(ll n){
    for(auto v : tr[n]){
        ls.push_back(id[{v, n}]);
        d[v] = d[n]+1; dfs(v);
    }
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
    A = B = 0; m = U.size();
    for(i=0;i<m;i++) q.push_back(0);
    for(i=0;i<m;i++){
        x = U[i], y = V[i];
        id[{x,y}]=id[{y,x}]=i;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    st = ask(q);
    lo = 1, hi = m;
    while(lo<hi){
        ll m = lo+hi>>1;
        sett(m);
        bool heh = (ask(q)==st);
        if(heh) lo=m+1;
        else hi=m;
    }
    mm = lo-1; sett(mm);
    x = U[mm+1], y = V[mm+1];
    qq.push(x); qq.push(y); vis[x]=vis[y]=1;
    while(qq.size()){
        x = qq.front(); qq.pop();
        for(auto v : adj[x]){
            if(id[{x,v}]>mm&&!vis[v]){
                vis[v] = 1;
                qq.push(v);
                tr[x].push_back(v);
                u[id[{x,v}]]=1;
            }
        }
    }
    u[mm+1]=1;
    x = U[mm+1], y = V[mm+1];
    dfs(x);
    lo = 0; hi = ls.size();
    while(lo<hi){
        ll mmm = lo+hi>>1;
        for(i=0;i<m;i++) q[i]=!u[i];
        for(i=mmm+1;i<ls.size();i++) q[ls[i]]=1;
        bool heh = (ask(q)==st);
        if(heh) hi=mmm;
        else lo=mmm+1;
    }
    if(lo==ls.size()){
        if(ls.empty()){s = U[mm+1];}
        else{
            x = U[ls[lo-1]], y = V[ls[lo-1]];
            if(d[x]>d[y]) s = x;
            else s = y;
        }
    }
    else{
        x = U[ls[lo]], y = V[ls[lo]];
        if(d[x]>d[y]) s = x;
        else s = y;
    }
    ls.clear();
    x = U[mm+1], y = V[mm+1];
    dfs(y);
    lo = 0; hi = ls.size();
    while(lo<hi){
        ll mmm = lo+hi>>1;
        for(i=0;i<m;i++) q[i]=!u[i];
        for(i=mmm+1;i<ls.size();i++) q[ls[i]]=1;
        bool heh = (ask(q)==st);
        if(heh) hi=mmm;
        else lo=mmm+1;
    }
    if(lo==ls.size()){
        if(ls.empty()){t = V[mm+1];}
        else{
            x = U[ls[lo-1]], y = V[ls[lo-1]];
            if(d[x]>d[y]) t = x;
            else t = y;
        }
    }
    else{
        x = U[ls[lo]], y = V[ls[lo]];
        if(d[x]>d[y]) t = x;
        else t = y;
    }
    answer(s, t);
}

Compilation message

highway.cpp: In function 'void sett(ll)':
highway.cpp:11:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<q.size();i++)
                 ~^~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:32:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll m = lo+hi>>1;
                ~~^~~
highway.cpp:57:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mmm = lo+hi>>1;
                  ~~^~~
highway.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=mmm+1;i<ls.size();i++) q[ls[i]]=1;
                     ~^~~~~~~~~~
highway.cpp:64:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(lo==ls.size()){
        ~~^~~~~~~~~~~
highway.cpp:82:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mmm = lo+hi>>1;
                  ~~^~~
highway.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=mmm+1;i<ls.size();i++) q[ls[i]]=1;
                     ~^~~~~~~~~~
highway.cpp:89:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(lo==ls.size()){
        ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 4652 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4856 KB Output is correct
2 Correct 44 ms 6952 KB Output is correct
3 Correct 489 ms 25452 KB Output is correct
4 Correct 535 ms 25460 KB Output is correct
5 Correct 561 ms 25868 KB Output is correct
6 Correct 469 ms 24676 KB Output is correct
7 Correct 466 ms 24412 KB Output is correct
8 Correct 570 ms 25936 KB Output is correct
9 Correct 445 ms 24552 KB Output is correct
10 Correct 510 ms 25032 KB Output is correct
11 Correct 375 ms 23740 KB Output is correct
12 Correct 556 ms 27992 KB Output is correct
13 Correct 547 ms 28520 KB Output is correct
14 Incorrect 597 ms 28364 KB Output is incorrect: {s, t} is wrong.

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 7824 KB Output is correct
2 Correct 63 ms 10792 KB Output is correct
3 Correct 93 ms 10460 KB Output is correct
4 Correct 278 ms 29284 KB Output is correct
5 Correct 274 ms 29484 KB Output is correct
6 Correct 284 ms 31856 KB Output is correct
7 Correct 233 ms 21236 KB Output is correct
8 Correct 274 ms 30500 KB Output is correct
9 Correct 239 ms 24324 KB Output is correct

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 4816 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 7092 KB Output is correct
2 Correct 59 ms 7248 KB Output is correct
3 Correct 631 ms 27508 KB Output is correct
4 Correct 736 ms 28436 KB Output is correct
5 Correct 750 ms 31528 KB Output is correct
6 Correct 768 ms 31972 KB Output is correct
7 Correct 790 ms 31708 KB Output is correct
8 Correct 731 ms 31948 KB Output is correct
9 Incorrect 526 ms 27140 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 7160 KB Output is correct
2 Correct 57 ms 7288 KB Output is correct
3 Correct 629 ms 27220 KB Output is correct
4 Correct 633 ms 27768 KB Output is correct
5 Correct 640 ms 28560 KB Output is correct
6 Incorrect 741 ms 32208 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -