oj.uz

Submission #1035619

# Submission time Handle Problem Language Result Execution time Memory
1035619 2024-07-26T12:31:17 Z Ludissey Highway Tolls (IOI18_highway) C++14
51 / 100
 453 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define int long long
#define all(x) (x).begin(), (x).end()
using namespace std;
vector<int> depth;
vector<pair<int,int>> parent;
vector<int> sz;
vector<vector<pair<int,int>>> child;
vector<vector<pair<int,int>>> neigh;
vector<vector<pair<int,int>>> neigh2;
vector<signed> aska;
int S=-1;
int M,N;
int shortest;
int totCount=0;
int prevP=0;
int getSIZE(int x){
    sz[x]=1;
    for (auto u : child[x])
    {
        sz[x]+=getSIZE(u.first);
    }
    return sz[x];
}
int find_centroid(int _x){
    int x = _x;
    int sizeT=sz[_x];
    while (true) {
        int c = -1;
        for (int i = 0; i < sz(child[x]); i++) {
            if (sz[child[x][i].first]>sizeT/2) c = child[x][i].first;
        }
        //if (sz[x]-1>sizeT/2&&parent[x].first!=-1) c = parent[x].first;
        if (c!=-1) x = c; 
        else break;
    }
    return x;
}
 
void reroot(int R){
    child.clear();
    parent.clear();
    child.resize(N);
    parent.resize(N);
    queue<pair<int,int>> q;
    q.push({R,-1});
    parent[R]={-1,-1};
    while(!q.empty()){
        int x=q.front().first,p=q.front().second; q.pop();
        for (auto u : neigh2[x])
        {
            if(u.first==p||u.first==-1) continue;
            child[x].push_back(u);
            parent[u.first]={x,u.second};
            q.push({u.first,x});
        }
    }
}
 
void colorSubtree(int x){
    aska[parent[x].second]=1;
    for (auto u : child[x])
    {
        colorSubtree(u.first);
    }
}
 
int findTree(int x){
    int l=0, r=sz(child[x])-1;
    aska.resize(M);
    int ans=-1;
    while(l<=r){
        for (int i = 0; i < M; i++) aska[i]=0;
        int mid=(l+r)/2;
        for (int i = 0; i <= mid; i++)
        {
            colorSubtree(child[x][i].first);
        }
        totCount++;
        if(ask(aska)>shortest){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
        
    }
    if(ans<0) {
        for (int i = 0; i < M; i++) aska[i]=0;
        if(parent[x].first>-1) {
            aska[parent[x].second]=1;
            if(ask(aska)>shortest){
                S=x;
                return S;
            }
            for (int i = 0; i < sz(neigh2[parent[x].first]); i++)
            {
                if(neigh2[parent[x].first][i].first==x){
                    neigh2[parent[x].first][i].first=-1;
                }
            }
            return prevP;
        }
        S=x;
        return S;
    }
    else{
        for (int i = 0; i < sz(neigh2[child[x][ans].first]); i++)
        {
            if(neigh2[child[x][ans].first][i].first==x){
                neigh2[child[x][ans].first][i].first=-1;
            }
        }
        return child[x][ans].first;
    }
}
 
void find_pair(signed n, std::vector<signed> U, std::vector<signed> V, signed A, signed B){
    M=sz(U);
    N=n;
    neigh.resize(N);
    neigh2.resize(N);
    child.resize(N);
    sz.resize(N);
    depth.resize(N);
    parent.resize(N);
    vector<signed> ep(M,0);
    shortest=ask(ep);
    int initDist=shortest/A;
    totCount=0;
    for (int i = 0; i < M; i++)
    {
        neigh[U[i]].push_back({V[i],i});
        neigh[V[i]].push_back({U[i],i});
        neigh2[U[i]].push_back({V[i],i});
        neigh2[V[i]].push_back({U[i],i});
    }
    int c=0;
    reroot(0);
    while(S<0){
        //cerr<<c<<"\n";
        prevP=c;
        getSIZE(c);
        int _c=find_centroid(c);
        _c=findTree(_c);
        c=_c;
        reroot(c);
        if(sz(child[c])==0) {
            S=c;
        }
    }
 
    vector<int> possible;
    queue<pair<int,int>> q;
    q.push({S,-1});
    child.clear();
    parent.clear();
    depth.clear();
    neigh.resize(N);
    child.resize(N);
    depth.resize(N);
    parent.resize(N);
    depth[S]=0;
    while(!q.empty()){
        int x=q.front().first,p=q.front().second; q.pop();
        if(depth[x]==initDist) possible.push_back(x);
        for (auto u : neigh[x])
        {
            if(u.first==p) continue;
            child[x].push_back(u);
            depth[u.first]=depth[x]+1;
            parent[u.first]={x,u.second};
            q.push({u.first,x});
        }
    }
    int l=0; int r=sz(possible)-1;
    while(l<r){
        int mid=(l+r)/2;
        vector<signed> w(M,0);
        for (int i = l; i <= mid; i++) { w[parent[possible[i]].second]=1; }
        if(ask(w)>shortest){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    answer(S,(int)possible[l]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 14 ms 2868 KB Output is correct
3 Correct 156 ms 23792 KB Output is correct
4 Correct 142 ms 23652 KB Output is correct
5 Correct 150 ms 23676 KB Output is correct
6 Correct 154 ms 23780 KB Output is correct
7 Correct 155 ms 23716 KB Output is correct
8 Correct 143 ms 23668 KB Output is correct
9 Correct 147 ms 23848 KB Output is correct
10 Correct 152 ms 23660 KB Output is correct
11 Correct 166 ms 24712 KB Output is correct
12 Correct 152 ms 24952 KB Output is correct
13 Correct 156 ms 24592 KB Output is correct
14 Correct 158 ms 24224 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3416 KB Output is correct
2 Correct 19 ms 6412 KB Output is correct
3 Correct 28 ms 9296 KB Output is correct
4 Correct 87 ms 27480 KB Output is correct
5 Correct 90 ms 27464 KB Output is correct
6 Correct 90 ms 27188 KB Output is correct
7 Correct 80 ms 27448 KB Output is correct
8 Correct 86 ms 27204 KB Output is correct
9 Correct 76 ms 27448 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 11 ms 2904 KB Output is correct
3 Correct 92 ms 18424 KB Output is correct
4 Correct 126 ms 23516 KB Output is correct
5 Correct 115 ms 23516 KB Output is correct
6 Correct 124 ms 23536 KB Output is correct
7 Correct 117 ms 23888 KB Output is correct
8 Correct 116 ms 23492 KB Output is correct
9 Correct 139 ms 23536 KB Output is correct
10 Correct 125 ms 23920 KB Output is correct
11 Correct 154 ms 24164 KB Output is correct
12 Correct 156 ms 25040 KB Output is correct
13 Correct 168 ms 24688 KB Output is correct
14 Correct 163 ms 25084 KB Output is correct
15 Correct 126 ms 23556 KB Output is correct
16 Correct 135 ms 23296 KB Output is correct
17 Correct 163 ms 24816 KB Output is correct
18 Correct 165 ms 24528 KB Output is correct
19 Correct 157 ms 23652 KB Output is correct
20 Correct 160 ms 25352 KB Output is correct
21 Correct 107 ms 24940 KB Output is correct
22 Correct 125 ms 24816 KB Output is correct
23 Correct 138 ms 23648 KB Output is correct
24 Correct 120 ms 24176 KB Output is correct
25 Correct 181 ms 27220 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 446 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 453 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -