oj.uz

답안 #113866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113866 2019-05-29T00:05:50 Z thebes 통행료 (IOI18_highway) C++14
0 / 100
 52 ms 13372 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 = 1; hi = ls.size();
    while(lo<hi){
        ll m = lo+hi>>1;
        for(i=0;i<m;i++) q[i]=!u[i];
        for(i=m+1;i<ls.size();i++) q[ls[i]]=1;
        bool heh = (ask(q)==st);
        if(heh) lo=m+1;
        else hi=m;
    }
    x = U[ls[lo-1]], y = V[ls[lo-1]];
    if(d[x]>d[y]) s = x;
    else s = y;
    ls.clear();
    x = U[mm+1], y = V[mm+1];
    dfs(y);
    lo = 1; hi = ls.size();
    while(lo<hi){
        ll m = lo+hi>>1;
        for(i=0;i<m;i++) q[i]=!u[i];
        for(i=m+1;i<ls.size();i++) q[ls[i]]=1;
        bool heh = (ask(q)==st);
        if(heh) lo=m+1;
        else hi=m;
    }
    x = U[ls[lo-1]], y = V[ls[lo-1]];
    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:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll m = lo+hi>>1;
                ~~^~~
highway.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=m+1;i<ls.size();i++) q[ls[i]]=1;
                   ~^~~~~~~~~~
highway.cpp:72:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll m = lo+hi>>1;
                ~~^~~
highway.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=m+1;i<ls.size();i++) q[ls[i]]=1;
                   ~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 9464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 39 ms 13372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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