QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#150533#6660. 택시 여행penguinman0 292ms51956kbC++176.3kb2023-08-25 20:09:252023-08-25 20:09:26

Judging History

你现在查看的是最新测评结果

  • [2023-08-25 20:09:26]
  • 评测
  • 测评结果:0
  • 用时:292ms
  • 内存:51956kb
  • [2023-08-25 20:09:25]
  • 提交

answer

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

constexpr ll inf = (1ll<<60);


std::vector<long long> travel(std::vector<long long> A,
        std::vector<int> B, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    ll N = A.size();
    vii edge(N), weight(N), d_edge(N);
    rep(i,0,N-1){
        edge[U[i]].pb(V[i]);
        edge[V[i]].pb(U[i]);
        weight[U[i]].pb(W[i]);
        weight[V[i]].pb(W[i]);
    }
    vi dist(N, -1), par(N), hld_dist(N);
    {
        std::queue<ll> que;
        vector<bool> visited(N);
        dist[0] = 0;
        que.push(0);
        while(!que.empty()){
            ll now = que.front(); que.pop();
            rep(i,0,edge[now].size()){
                ll next = edge[now][i];
                if(dist[next] != -1) continue;
                dist[next] = dist[now]+weight[now][i];
                que.push(next);
                par[next] = now;
                d_edge[now].pb(next);
                hld_dist[next] = hld_dist[now]+1;
            }
        }
    }
    vi c_par(N,-1);
    vector<bool> dead(N);

    vi subtree(N);

    std::function<void(ll)> calc_subtree = [&](ll now){
        subtree[now] = 1;
        for(auto next: d_edge[now]){
            if(dead[next]) continue;
            calc_subtree(next);
            subtree[now] += subtree[next];
        }
    };

    // hld

    vi hld_par(N);

    std::function<void(ll)> heavy_light_decomposition = [&](ll now){
        rep(i,1,d_edge[now].size()){
            if(subtree[edge[now][0]] < subtree[edge[now][i]]) std::swap(edge[now][i], edge[now][0]);
        }
        rep(i,0,d_edge[now].size()){
            ll next = d_edge[now][i];
            if(i) hld_par[next] = next;
            else hld_par[next] = hld_par[now];
            heavy_light_decomposition(next);
        }
    };

    auto LCA = [&](ll l, ll r){
        while(true){
            if(hld_dist[l] < hld_dist[r]) std::swap(l,r);
            if(hld_par[l] == hld_par[r]){
                return r;
            }
            if(l == hld_par[l]) l = par[l];
            else l = hld_par[l];
        }
    };

    auto distance = [&](ll l, ll r){
        return dist[l]+dist[r]-2*dist[LCA(l,r)];
    };

    calc_subtree(0);
    heavy_light_decomposition(0);

    // centroid tree
    
    std::function<ll(ll, ll)> find_centroid = [&](ll root, ll now){
        ll max = subtree[root]-subtree[now];
        for(auto next: d_edge[now]){
            if(dead[next]) continue;
            ll c = find_centroid(root, next);
            if(c != -1) return c;
            max = std::max(max, subtree[next]);
        }
        if(max*2 <= subtree[root]) return now;
        return ll(-1);
    };
    std::function<void(ll,ll)> centroid_coloring = [&](ll centroid, ll now){
        if(now != centroid) c_par[now] = centroid;
        for(auto next: d_edge[now]){
            if(dead[next]) continue;
            centroid_coloring(centroid, next);
        }
    };

    std::function<void(ll)> dfs_centroid_decomposition = [&](ll root){
        if(dead[root]) return;
        calc_subtree(root);
        if(subtree[root] == 1) return;
        ll c = find_centroid(root,root);
        centroid_coloring(c, root);
        dead[c] = true;
        for(auto next: d_edge[c]){
            dfs_centroid_decomposition(next);
        }
        dfs_centroid_decomposition(root);
    };

    dfs_centroid_decomposition(0);

    vector<pii> data(N);
    rep(i,0,N) data[i] = mp(B[i], i);
    sort(all(data));
    reverse(all(data));

    vector<vector<pii>> lines(N);

    // m について判定
    // is_need : true → m は必要
    auto is_need = [&](pii l, pii m, pii r){
        return ((r.second-m.second)*(m.first-l.first) < (m.second-l.second)*(r.first-m.first));
    };

    auto add_line = [&](ll idx, pii l){
        if(!lines[idx].empty() && lines[idx].back().first == l.first){
            ll n = lines[idx].size();
            if(lines[idx][n-1].second <= l.second) return;
            lines[idx].pop_back();
        }

        while(lines[idx].size() > 1){
            ll n = lines[idx].size();
            if(!is_need(lines[idx][n-2], lines[idx][n-1], l)) lines[idx].pop_back();
            else break;
        }

        lines[idx].pb(l);
    };

    auto value = [&](pii f, ll x){
        return f.first*x+f.second;
    };

    auto calc = [&](ll idx, ll x){
        if(lines[idx].empty()) return inf;
        /*{
            ll min = inf;
            for(auto el: lines[idx]){
                min = std::min(min, value(el, x));
                cout << value(el, x) << " ";
            }
            cout << endl;
            return min;
        }*/
        ll left = 0, right = lines[idx].size();
        while(left+1 < right){
            ll mid = (left+right)/2;
            if(value(lines[idx][mid-1],x) > value(lines[idx][mid], x)) left = mid;
            else right = mid;
        }
        return value(lines[idx][left], x);
    };

    vi ans(N, inf);
    ans[0] = 0;

    for(auto el: data){
        ll now = el.second;
        ll n_v = now;
        while(true){
            ans[now] = std::min(ans[now], calc(n_v, distance(now, n_v)));
            if(c_par[n_v] == -1) break;
            n_v = c_par[n_v];
        }
        n_v = now;
        while(true){
            add_line(n_v, mp(B[now], A[now]+ans[now]+distance(now, n_v)*B[now]));
            if(c_par[n_v] == -1) break;
            n_v = c_par[n_v];
        }
    }
    rep(now,0,N){
        ll n_v = now;
        while(true){
            ans[now] = std::min(ans[now], calc(n_v, distance(now, n_v)));
            if(c_par[n_v] == -1) break;
            n_v = c_par[n_v];
        }
    }
    {
        reverse(all(ans));
        ans.pop_back();
        reverse(all(ans));
    }
    return ans;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 7
Accepted
time: 1ms
memory: 3784kb

input:

2
684124582850 713748627948
74361 256955
0 1 661088

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
733283747618
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

ok 3 lines

Test #2:

score: -7
Wrong Answer
time: 1ms
memory: 3664kb

input:

3
251115773325 363097865287 358609487841
826785 213106 914768
0 1 851938
2 0 231697

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
955485332655
1549512318252
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

wrong answer 3rd lines differ - expected: '442679377470', found: '1549512318252'

Subtask #2:

score: 0
Wrong Answer

Test #31:

score: 0
Wrong Answer
time: 292ms
memory: 51956kb

input:

100000
746699125678 374834842799 250803643493 620187038832 454433387570 406226564003 897157438699 99473514061 734784419618 503968957100 363935477037 277126009840 52078020050 990757079812 847235285349 950784717285 271017141367 861087225700 996035427219 520682200664 282013988419 415183977876 882007771...

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
1148030742334
1636760433058
2131282232650
2353514637869
2672707119337
2885076006601
2948215735597
3003888852169
3054019822989
3117708941277
3168979051095
3214001638323
3269286229765
3273106480907
3287227043365
3335909595067
3361857042147
3364657567217
338173015...

result:

wrong answer 7th lines differ - expected: '2763307672337', found: '2885076006601'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 17
Accepted
time: 115ms
memory: 37412kb

input:

100000
15175010 23519365 21177669 27079342 9089 16784452 29693960 23124925 17048604 10179491 12828214 24992902 8483134 2928073 23807522 7332137 17421520 28460746 1607282 13224363 11900728 11794692 11495061 4687109 23460275 7657982 27417256 16978162 7326803 23083826 24942987 16610314 12147303 2828271...

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
16705757
...

result:

ok 100001 lines

Test #70:

score: -17
Wrong Answer
time: 154ms
memory: 37904kb

input:

100000
3100890 18869608 28100950 22925442 5793993 25887606 5712025 16783243 22490605 7223603 27212909 19749276 22470322 1196820 23308444 12318305 13271014 12850212 19296071 20606196 7506157 10805123 4563831 23592776 15092259 13668900 4494974 28314546 9688373 16660275 26653405 20265376 23328402 65821...

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17254147
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
17520670
...

result:

wrong answer 2nd lines differ - expected: '10152436', found: '17520670'

Subtask #5:

score: 0
Wrong Answer

Test #94:

score: 0
Wrong Answer
time: 78ms
memory: 37000kb

input:

99281
551670361798 568902251563 418071776626 697635341894 641578820039 117221079324 812766431051 425410617978 663769685693 282144284527 799662290178 749088952784 586626406385 122473825417 459510657357 871705247919 443707710712 735612808044 237919555727 829939639783 122127143240 616906466299 24431898...

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1...

result:

wrong answer 2nd lines differ - expected: '598598746654', found: '1152921504606846976'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%