Submission #782323

#	Time	Username	Problem	Language	Result	Execution time	Memory
782323		anton	Construction of Highway (JOI18_construction)	C++17	16 / 100	2073 ms	59816 KiB

construction

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
vector<int> colors;
vector<int> time_g;
vector<int> depth;

map<int, int> m;
struct Node{
    int t;
    int last_m;
    int color;
    mutable vector<pii> cols;

    bool operator<( const Node& b)const{
        return t<b.t;
    }

    Node(int id){
        t = time_g[id];
        color = colors[id];
        last_m =id;
        //cols.push_back(pii(depth[id]-1, color));
    }
};
vector<vector<pii>> adj;

void merge_pure(set<Node>&s, set<Node>&b, int prov){
    for(auto e: b){
        auto e2 = e;
        e2.last_m = prov;
        s.insert(e);
    }
}

void compute_rel(set<Node>::iterator a, set<Node>::iterator b, int d){
    //cout<<a->t<<" "<<b->t<<endl;
    if(a->last_m!=b->last_m){
        //cout<<m[a->t]+1<<" includes "<<m[b->t]+1<<endl;
        a->cols.push_back(pii(d, b->color));
    }
}

void merge(set<Node>&a, set<Node>& b, int id){
    for(auto it = b.begin(); it!=b.end(); it++){
        auto pre = a.lower_bound((*it));

        if(pre!=a.end()){
            it++;
            if(it== b.end() || pre->t<it->t){
                it--;
                compute_rel(pre, it, depth[id]);
                it++;
            }
            it--;
        }
        if(pre!=a.begin()){
            pre--;
            if(pre!=a.end() && ((*pre)<(*it))){
                //cout<<"pre "<<pre->t<<" "<<it->t<<endl;
                //cout<<((*pre)<(*it))<<endl;
                compute_rel(it, pre, depth[id]);
                
            }
        }
        a.insert(*it);
    }

}
set<Node> dfs(int id){
    set<Node> res;
    
    set<Node> comp;
    if(adj[id].size()>0){
        vector<set<Node>> sub;
        pii best = pii(0, 0);
        for(auto ch: adj[id]){
            sub.push_back(dfs(ch.first));
            if(sub.back().size()>best.first){
                best.first = sub.back().size();
                best.second = sub.size()-1;
            }
        }
        swap(res, sub[best.second]);
        for(int i = 0; i<sub.size(); i++){
            if(i != best.second){
                merge_pure(comp, sub[i],adj[id][i].first);
            }
        }

    }

        
    comp.insert(Node(id));
    merge(res, comp, id);
    //cout<<id<<endl;

    for(auto e: res){
        //cout<<m[e.t]+1<<" | ";
    }
    //cout<<endl<<endl<<endl;
    return res;
}

int merge(vector<pii>&v, int lt, int rt, int mid){

    //cout<<"merging "<<lt<<" "<<rt<<" "<<mid<<endl;
    
    vector<pii> res;
    int c= 0;
    int l = lt;
    int r= mid+1;

    int r_s =0;
    for(int i = lt; i<=rt; i++){
        if(l>mid){
            res.push_back(v[r]);
            r_s += v[r].first;
            r++;
        }
        else if(r>rt){
            res.push_back(v[l]);
            c+=(r_s)*v[l].first;
            l++;
        }
        else if(v[l].second<=v[r].second){
            res.push_back(v[l]);
            c+=(r_s)*v[l].first;
            l++;
        }
        else{
            res.push_back(v[r]);
            r_s += v[r].first;
            r++;
        }
    }

    for(int i = lt; i<=rt; i++){
        v[i] = res[i-lt];
    }
    return c;
}

int dpr(vector<pii>&v, int lt, int rt){
    if(lt==rt){
        return 0;
    }
    else{
        //cout<<lt<<" "<<rt<<endl;
        int mid = (lt+rt)/2;
        int r =0;
        r+=dpr(v, lt, mid);
        r+=dpr(v, mid+1, rt);
        r+= merge(v, lt, rt, mid);
        //cout<<r<<endl;
        return r;
    }
}

signed main(){
    int n;
    cin>>n;
    colors.resize(n);
    adj.resize(n);
    time_g.resize(n, -1);
    depth.resize(n, 1);

    for(int i = 0; i<n; i++){
        int c;
        cin>>c;
        colors[i] = c;
    }

    m.insert(pii(-1, 0));

    for(int i = 0; i<n-1; i++){
        int a, b;
        cin>>a>>b;
        a--;b--;
        time_g[b] = i;

        adj[a].push_back(pii(b, i));
        depth[b] = depth[a]+1;
        m.insert(pii(i, b));
    }

    set<Node> res = dfs(0);

    //cout<<res.size()<<endl;
    for(auto e: res){
        //cout<<"t: "<<m[e.t]+1<<" , ";
        for(auto c: e.cols){
            //cout<<m[c.first]+1<<" "<<c.second<<" | ";
        }
        //cout<<endl;
    }

    vector<int> ans(n-1);

    for(auto e: res){
        int cur= e.t;
        if(cur!=-1){

            int r= 0;

            sort(e.cols.begin(), e.cols.end());

            for(int i = e.cols.size()-1; i>0; i--){
                e.cols[i].first -=e.cols[i-1].first;
            }

            for(auto ee:e.cols){
                //cout<<ee.first<<" "<<ee.second<<" | ";
            }
            //cout<<endl;
            r += dpr(e.cols, 0, e.cols.size()-1);
            ans[cur]= r;
        }
    }

    //cout<<"_"<<endl;
    for(int i= 0; i<n-1; i++){
        cout<<ans[i]<<endl;
    }
}

Compilation message (stderr)

construction.cpp: In function 'std::set<Node> dfs(long long int)':
construction.cpp:81:33: warning: comparison of integer expressions of different signedness: 'std::set<Node>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   81 |             if(sub.back().size()>best.first){
      |                ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
construction.cpp:87:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::set<Node> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i = 0; i<sub.size(); i++){
      |                        ~^~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:194:18: warning: variable 'c' set but not used [-Wunused-but-set-variable]
  194 |         for(auto c: e.cols){
      |                  ^
construction.cpp:214:22: warning: variable 'ee' set but not used [-Wunused-but-set-variable]
  214 |             for(auto ee:e.cols){
      |                      ^~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84