Submission #35329

#	Time	Username	Problem	Language	Result	Execution time	Memory
35329		wan2000	도로 건설 사업 (JOI13_construction)	C++14	40 / 100	1756 ms	130992 KiB

construction

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

template<typename T> inline void read(T &x){
    x = 0; char ch;
    while(!isdigit(ch=getchar()));
    do{x=10*x+ch-'0';}while(isdigit(ch=getchar()));
}

typedef long long ll;

const int N = 2e5+111;

int n, m, k, pos[3*N], num, cnt, D[3*N], ID[3*N], Fa[N];
ll RD[3*N], F[N];
vector<pair<ll,int> > Adj[N];

struct pt{
    int x, y;
    ll rx, ry;
    pt(){}
    pt(int a, int b){
        x=a; y=b;
        rx = (ll)x; ry = (ll)y;
    }
} A[N], P[3*N];

struct rect{
    pt up, down;
    rect(){}
    rect(pt a, pt b){
        up = a; down = b;
    }
} B[N];

struct data{
    int x;
    int y, l, r;
    int type, id;
    ll rx;
    data(){}
    data(int a, int b, int c, int d, int e, int f, ll g){
        x = a; y = b; l = c; r = d; type = e; id = f; rx = g;
    }
};
vector<data> T;

struct Edge{
    int u, v;
    ll w;
    Edge(){}
    Edge(int a, int b, ll c){
        u = a; v = b; w = c;
    }
} E[4*N];

bool cmp_x(int a, int b){
    return P[a].x < P[b].x;
}

bool cmp_y(int a, int b){
    return P[a].y < P[b].y;
}

bool operator < (const data &a, const data &b){
    return a.x < b.x || (a.x==b.x&&a.type<b.type);
}

bool operator < (const Edge &a, const Edge &b){
    return a.w < b.w;
}

void compress(){
    num = n+2*m;
    for(int i = 1; i <= num; i++){
        pos[i] = i;
    }
    sort(pos+1,pos+num+1,cmp_x);
    cnt = 1;
    int cur = P[pos[1]].x;
    P[pos[1]].x = 1;
    for(int i = 2; i <= num; i++){
        if(P[pos[i]].x!=cur){
            cnt++;
            cur = P[pos[i]].x;
        }
        P[pos[i]].x = cnt;
    }
    sort(pos+1,pos+num+1,cmp_y);
    cnt = 1;
    cur = P[pos[1]].y;
    P[pos[1]].y = 1;
    for(int i = 2; i <= num; i++){
        if(P[pos[i]].y!=cur){
            cnt++;
            cur = P[pos[i]].y;
        }
        P[pos[i]].y = cnt;
    }
    for(int i = 1; i <= n; i++){
        A[i] = P[i];
    }
    for(int i = 1; i < 2*m; i+=2){
        B[i/2+1] = rect(P[i+n],P[i+n+1]);
    }
}

struct SegTree{
    int ST[12*N], Lazy[12*N];
    void reset(){
        memset(ST,0,sizeof(ST));
        memset(Lazy,0,sizeof(Lazy));
    }
    void down(int id, int l, int r){
        if(!Lazy[id]) return;
        ST[id] = max(ST[id],Lazy[id]);
        if(l!=r){
            Lazy[2*id] = max(Lazy[2*id],Lazy[id]);
            Lazy[2*id+1] = max(Lazy[2*id+1],Lazy[id]);
        }
        Lazy[id] = 0;
    }
    void upgrade(int id, int l, int r, int u, int v, int val){
        down(id,l,r);
        if(r<u||v<l) return;
        if(u<=l&&r<=v){
            Lazy[id] = max(Lazy[id],val);
            down(id,l,r);
            return;
        }
        int mid = (l+r)>>1;
        upgrade(2*id,l,mid,u,v,val);
        upgrade(2*id+1,mid+1,r,u,v,val);
        ST[id] = ST[2*id]+ST[2*id+1];
    }
    int get(int id, int l, int r, int x){
        down(id,l,r);
        if(x<l||r<x) return -1;
        if(l==r) return ST[id];
        int mid = (l+r)>>1;
        return max(get(2*id,l,mid,x),get(2*id+1,mid+1,r,x));
    }
} Tree;

void makeGraph(){
    sort(T.begin(),T.end());
    memset(D,255,sizeof(D));
    Tree.reset();
    for(int i = 0; i < (int)T.size(); i++){
        data dt = T[i];
        if(dt.type==0) Tree.upgrade(1,1,num,dt.l,dt.r,dt.x);
        else{
            if(D[dt.y]==-1){
                D[dt.y] = dt.x;
                ID[dt.y] = dt.id;
                RD[dt.y] = dt.rx;
            }
            else{
                int x = Tree.get(1,1,num,dt.y);
                int id = ID[dt.y];
                ll xx = RD[dt.y];
                if(D[dt.y]>x){
                    Adj[dt.id].push_back(mp((ll)abs(xx-dt.rx),id));
                    Adj[id].push_back(mp((ll)abs(xx-dt.rx),dt.id));
                }
                D[dt.y] = dt.x;
                RD[dt.y] = dt.rx;
                ID[dt.y] = dt.id;
            }
        }
    }
}

int root(int x){
    if(Fa[x]<0) return x;
    int t = root(Fa[x]);
    return Fa[x] = t;
}

void unite(int x, int y){
    if(Fa[x]<Fa[y]){
        Fa[x] += Fa[y];
        Fa[y] = x;
    }
    else{
        Fa[y] += Fa[x];
        Fa[x] = y;
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //read(n); read(m); read(k);
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++){
        int x, y;
        //read(x); read(y);
        cin>>x>>y;
        P[i] = pt(x,y);
    }
    for(int i = 1; i < 2*m; i+=2){
        //read(P[n+i].x); read(P[n+i].y);
        //read(P[n+i+1].x); read(P[n+i+1].y);
        cin>>P[n+i].x>>P[n+i].y>>P[n+i+1].x>>P[n+i+1].y;
    }
    compress();
    for(int i = 1; i <= n; i++){
        T.push_back(data(A[i].x,A[i].y,0,0,1,i,A[i].rx));
    }
    for(int i = 1; i <= m; i++){
        T.push_back(data(B[i].up.x,0,B[i].up.y,B[i].down.y,0,0,0));
        T.push_back(data(B[i].down.x,0,B[i].up.y,B[i].down.y,0,0,0));
    }
    makeGraph();
    T.clear();
    for(int i = 1; i <= n; i++){
        T.push_back(data(A[i].y,A[i].x,0,0,1,i,A[i].ry));
    }
    for(int i = 1; i <= m; i++){
        T.push_back(data(B[i].up.y,0,B[i].up.x,B[i].down.x,0,0,0));
        T.push_back(data(B[i].down.y,0,B[i].up.x,B[i].down.x,0,0,0));
    }
    makeGraph();
    int eNum = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < (int)Adj[i].size(); j++){
            E[++eNum] = Edge(i,Adj[i][j].Y,Adj[i][j].X);
        }
    }
    sort(E+1,E+eNum+1);
    memset(Fa,255,sizeof(Fa));
    int com = n;
    ll sum = 0;
    for(int i = 1; i <= eNum; i++){
        int u = E[i].u;
        int v = E[i].v;
        ll w = E[i].w;
        int ru = root(u);
        int rv = root(v);
        if(ru==rv) continue;
        unite(ru,rv);
        com--;
        sum += w;
        F[com] = sum;
    }
    while(k--){
        ll c;
        int h;
        //read(c); read(h);
        cin>>c>>h;
        if(h<com) cout<<-1<<endl;
        else{
            int l = com, r = h;
            int ml = floor((double)(l+l+r)/3);
            int mr = ceil((double)(l+r+r)/3);
            while(ml<mr){
                if(F[ml]+c*(ll)ml<F[mr]+c*(ll)mr) r = mr-1;
                else l = ml+1;
                ml = floor((double)(l+l+r)/3);
                mr = ceil((double)(l+r+r)/3);
            }
            ll res = F[ml]+c*(ll)ml;
            cout<<res<<endl;
        }
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30