답안 #802802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
802802 2023-08-02T14:41:24 Z fatemetmhr 통행료 (IOI18_highway) C++17
5 / 100
125 ms 19708 KB
//  ~ Be Name Khoda ~  //

#include "highway.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

vector <int> tok, adj[maxn5], v, u, ver, ed;
ll len;
int m, q[maxn5], par[maxn5], pas[maxn5];
bool mark[maxn5], good[maxn5];

void bfs(int rt){
    par[rt] = -1;
    memset(mark, false, sizeof mark);
    int l = 0, r = 1;
    q[0] = rt;
    mark[rt] = true;
    while(l < r){
        int a = q[l++];
        for(auto id : adj[a]){
            int b = u[id] == a ? v[id] : u[id];
            if(mark[b])
                continue;
            //cout << "here " << a << ' ' << b << ' ' << id << endl;
            good[id] = true;
            mark[b] = true;
            q[r++] = b;
            par[b] = a;
        }
    }
}

void dfs(int v){
    //cout << v << ' ' << par[v] << endl;
    for(auto id : adj[v]) if(good[id]){
        int u = (::u[id]) == v ? (::v[id]) : (::u[id]);
        if(u == par[v])
            continue;
        //cout << "in " << v << ' ' << u << ' ' << id << endl;
        dfs(u);
        ver.pb(u);
        ed.pb(id);
    }
}

ll get(int id){
    if(pas[id] == -1){
        fill(all(tok), 1);
        for(auto u : ed)
            tok[u] = false;
        for(int i = 0; i <= id; i++)
            tok[ed[i]] = true;
        pas[id] = ask(tok);
    }
    return pas[id];
}


void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b){
    memset(pas, -1, sizeof pas);
    u = U;
    v = V;
    m = u.size();
    for(int i = 0; i < m; i++){
        adj[u[i]].pb(i);
        adj[v[i]].pb(i);
    }
    int lo = -1, hi = n;
    tok.resize(m);
    fill(all(tok), 0);
    len = ask(tok) / a;
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        fill(all(tok), 0);
        for(int i = 0; i <= mid; i++)
            for(auto id : adj[i])
                tok[id] = 1;
        ll cost = ask(tok);
        if(cost == len * a)
            lo = mid;
        else
            hi = mid;
    }
    assert(hi < n);
    par[hi] = -1;
    bfs(hi);
    //return;
    dfs(hi);
    /*
    for(int i = 0; i < n - 1; i++)
        cout << ed[i] << ' ' << ver[i] << endl;
    //*/
    //cout << "its " << hi << endl;
    lo = -1; hi = n - 1;
    ll x;
    int lim = 60000;
    if(false && n > lim + 5){
        x = get(lim);
        if(x == len * a){
            lo = lim;
            hi = n - 1;
        }
        else{
            lo = -1;
            hi = lim;
        }
    }
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        if(get(mid) == len * a)
            lo = mid;
        else
            hi = mid;
    }
    int s = ver[hi];
    //cout << "here " << lo << ' ' << hi << ' ' << s << endl;
    if(false && n > lim + 5){
        if(x == len * b){
            hi = lim;
            lo = -1;
        }
        else{
            lo = lim;
            hi = n - 1;
        }
    }
    else{
        lo = -1;
        hi = n - 1;
    }
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        //cout << mid << ' ' << get(mid) << ' ' << len << ' ' << a << ' ' << b << endl;
        if(get(mid) == len * b)
            hi = mid;
        else
            lo = mid;
    }
    int v = s;
    bool re = false;
    while(v != -1){
        if(v == ver[hi])
            re = true;
        v = par[v];
    }
    int t;
    if(re)
        t = par[ver[hi]];
    else
        t = ver[hi];
    //cout << re << ' ' << hi << ' ' << lo << ' ' << t << endl;
    answer(s, t);
    return;

}














# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5968 KB Output is correct
2 Correct 3 ms 5968 KB Output is correct
3 Correct 3 ms 5964 KB Output is correct
4 Correct 3 ms 5968 KB Output is correct
5 Correct 3 ms 5968 KB Output is correct
6 Correct 3 ms 5968 KB Output is correct
7 Correct 3 ms 5968 KB Output is correct
8 Correct 3 ms 5968 KB Output is correct
9 Correct 3 ms 5968 KB Output is correct
10 Correct 3 ms 5968 KB Output is correct
11 Correct 3 ms 5968 KB Output is correct
12 Correct 3 ms 5968 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5968 KB Output is correct
2 Correct 12 ms 6740 KB Output is correct
3 Correct 108 ms 13076 KB Output is correct
4 Correct 101 ms 13012 KB Output is correct
5 Correct 125 ms 13008 KB Output is correct
6 Correct 116 ms 13016 KB Output is correct
7 Correct 95 ms 13012 KB Output is correct
8 Correct 111 ms 13012 KB Output is correct
9 Correct 107 ms 13012 KB Output is correct
10 Correct 88 ms 13044 KB Output is correct
11 Correct 98 ms 14724 KB Output is correct
12 Correct 117 ms 15488 KB Output is correct
13 Correct 110 ms 14864 KB Output is correct
14 Incorrect 106 ms 14172 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7376 KB Output is correct
2 Correct 24 ms 8908 KB Output is correct
3 Correct 33 ms 10404 KB Output is correct
4 Correct 89 ms 17340 KB Output is correct
5 Correct 94 ms 17504 KB Output is correct
6 Correct 72 ms 18688 KB Output is correct
7 Correct 85 ms 19708 KB Output is correct
8 Correct 101 ms 18004 KB Output is correct
9 Incorrect 92 ms 18232 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5968 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 6868 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 6868 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -