oj.uz

답안 #86611

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
86611 2018-11-27T03:34:24 Z long10024070 도로 건설 사업 (JOI13_construction) C++11
0 / 100
 1033 ms 127728 KB 
#define Link "https://dunjudge.me/analysis/problems/980/?fbclid=IwAR0lz5NJ1ferKp5nADDwgoLiHvUbIE48RZqI5DtvPEqUlf-6RFpMV2Thm_c"

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define TASK "Construction Project"

using namespace std;

const int maxsz = 2e5 * 4;
const int maxn = 2e5;
int n,m,c,x[maxn],y[maxn],p[maxn],q[maxn],r[maxn],s[maxn],Truex[maxsz],Truey[maxsz];
int node[maxsz];
vector <int> add[maxsz],sub[maxsz],mem[maxsz];
int cntedge,u[maxsz],v[maxsz],w[maxsz],id[maxsz];
int lab[maxsz];
vector <int> chose;

void Enter()
{
    cin >> n >> m >> c;
    for (int i=1;i<=n;++i)
        cin >> x[i] >> y[i];
    for (int i=1;i<=m;++i)
        cin >> p[i] >> q[i] >> r[i] >> s[i];
}

void Analyze(int a[], int b[], int c[], int True[])
{
    vector <int*> v;
    for (int i=1;i<=n;++i)
        v.push_back(&a[i]);
    for (int i=1;i<=m;++i)
        v.push_back(&b[i]);
    for (int i=1;i<=m;++i)
        v.push_back(&c[i]);
    sort(v.begin(),v.end(),
         [] (int *i, int *j)
         {
             return *i < *j;
         });
    int cnt = 0;
    int pre = -1;
    for (auto p : v) {
        if (*p != pre) {
            ++cnt;
//            cout << *p << ' ';
            True[cnt] = pre = *p;
        }
        *p = cnt;
    }
//    cout << '\n' << '\n';;
}

void Update(int i, int d)
{
    for (;i<maxsz;i+=i&-i) {
        node[i] += d;
//        cout << i << ' ' << node[i] << "   " ;
    }
//    cout << '\n';
}

int Query(int i)
{
    int res = 0;
//    cout << i << '\n';
    for (;i>0;i&=(i-1)) {
        res += node[i];
//        cout << i << ' ' << node[i] << "   " ;
    }
//    cout << '\n';
    return res;
}

int QuerySum(int l, int r)
{
//    cout << l << ' ' << r << ' ' << Query(r) << ' ' << Query(l-1) << '\n';
    return Query(r) - Query(l-1);
}

void BuildGraph()
{
    for (int Y=1;Y<maxsz;++Y) {
        add[Y].clear();
        sub[Y].clear();
        mem[Y].clear();
    }
    fill(node,node+maxsz,0);
    for (int i=1;i<=m;++i) {
        add[q[i]].push_back(i);
        sub[s[i]+1].push_back(i);
    }
    for (int i=1;i<=n;++i)
        mem[y[i]].push_back(i);
    for (int Y=1;Y<maxsz;++Y) {
        for (int i : add[Y]) {
//            cout << p[i] << ' ' << r[i] << " +1" << '\n';
            Update(p[i],+1);
//            Update(r[i]+1,-1);
        }
        for (int i : sub[Y]) {
//            cout << p[i] << ' ' << r[i] << " -1" << '\n';
            Update(p[i],-1);
//            Update(r[i]+1,+1);
        }
        sort(mem[Y].begin(),mem[Y].end(),
             [] (int i, int j)
             {
                 return x[i] < x[j];
             });
        for (int t=0;t+1<mem[Y].size();++t) {
            int i1 = mem[Y][t];
            int i2 = mem[Y][t+1];
//            cout << i1 << ' ' << i2 << ' ' << x[i1] << ' ' << x[i2] << ' ' << Truex[x[i1]] << ' ' << Truex[x[i2]] << ' ' << QuerySum(x[i1],x[i2]) << '\n';
            if (QuerySum(x[i1],x[i2]) == 0) {
                ++cntedge;
                u[cntedge] = i1;
                v[cntedge] = i2;
                w[cntedge] = Truex[x[i2]] - Truex[x[i1]];
            }
        }
    }
}

void Init()
{
    Analyze(x,p,r,Truex);
    Analyze(y,q,s,Truey);
    BuildGraph();
    swap(x,y);
    swap(q,p);
    swap(r,s);
    swap(Truex,Truey);
    BuildGraph();
    swap(x,y);
    swap(q,p);
    swap(r,s);
    swap(Truex,Truey);
}

int Find_set(int n)
{
    return lab[n] > 0 ? lab[n] = Find_set(lab[n]) : n;
}

bool Union(int s, int t)
{
    if (s == t)
        return 0;
    if (lab[s] > lab[t])
        swap(s,t);
    lab[s] += lab[t];
    lab[t] = s;
    return 1;
}

void Solve()
{
    for (int i=1;i<=cntedge;++i)
        id[i] = i;
    sort(id+1,id+cntedge+1,
         [] (int i, int j)
         {
             return w[i] < w[j];
         });
    for (int t=1;t<=cntedge;++t) {
        int i = id[t];
        if (Union(Find_set(u[i]),Find_set(v[i]))) {
//            cout << u[i] << ' ' << v[i] << ' ' << w[i] << '\n';
            chose.push_back(w[i]);
        }
    }
    int n2 = chose.size();
    chose.push_back(0);
    sort(chose.begin(),chose.end());
    for (int i=1;i<=n2;++i)
        chose[i] += chose[i-1];
    for (int i=1;i<=c;++i) {
        int b,h;
        cin >> b >> h;
//        cout << b << ' ' << h << ' ' << n << ' ' << n2 << '\n';
        h -= n - n2;
        if (h >= 0) {
            int l = max(n2 - h, 1);
            int r = n2;
            while (l <= r) {
                int m = (l + r) / 2;
                if (chose[m] - chose[m-1] <= b)
                    l = m + 1;
                else
                    r = m - 1;
            }
            cout << chose[r] + 1ll * b * (n - r) << '\n';
        }
        else
            cout << -1 << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

#ifdef LHL
    freopen(".INP","r",stdin);
    freopen(".OUT","w",stdout);
#else
//    freopen(TASK".INP","r",stdin);
//    freopen(TASK".OUT","w",stdout);
#endif // LHL

    Enter();
    Init();
    Solve();
}

Compilation message

construction.cpp: In function 'void BuildGraph()':
construction.cpp:114:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int t=0;t+1<mem[Y].size();++t) {
                      ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 121 ms 71932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1033 ms 112824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 388 ms 112824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1000 ms 127728 KB Output isn't correct
2 Halted 0 ms 0 KB -