oj.uz

Submission #283699

# Submission time Handle Problem Language Result Execution time Memory
283699 2020-08-26T05:46:33 Z 최은수(#5746) 도로 건설 사업 (JOI13_construction) C++14
0 / 100
 306 ms 17240 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct dsu
{
    int pa[mx];
    int par(int x)
    {
        if(pa[x]==0)
            return x;
        return pa[x]=par(pa[x]);
    }
    inline void uni(int x,int y)
    {
        x=par(x);
        y=par(y);
        if(x==y)
            return;
        pa[x]=y;
        return;
    }
}uf;
vector<pi>xyed;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,c;
    cin>>n>>m>>c;
    vector<pi>v(n);
    for(pi&t:v)
        cin>>t.fi>>t.se;
    vector<int>sv;
    for(int i=0;i<n;i++)
        sv.eb(i);
    sort(all(sv),[&](const int&x,const int&y){return v[x]<v[y];});
    for(int i=1;i<n;i++)
        if(v[sv[i]].fi==v[sv[i-1]].fi)
            xyed.eb(sv[i-1],sv[i]);
    sort(all(sv),[&](const int&x,const int&y){return pi(v[x].se,v[x].fi)<pi(v[y].se,v[y].fi);});
    for(int i=1;i<n;i++)
        if(v[sv[i]].se==v[sv[i-1]].se)
            xyed.eb(sv[i-1],sv[i]);
    vector<pair<pi,pi> >mv(m);
    for(auto&t:mv)
        cin>>t.fi.fi>>t.se.fi>>t.fi.se>>t.se.se;
    vector<pair<int,pi> >ev;
    vector<int>wv;
    for(pi&e:xyed)
    {
        bool f=1;
        for(auto&t:mv)
        {
            if(t.fi.fi<=v[e.se].fi&&v[e.fi].fi<=t.fi.se&&t.se.fi<=v[e.se].se&&v[e.fi].se<=t.se.se)
            {
                f=0;
                break;
            }
        }
        if(f)
            ev.eb(v[e.se].fi-v[e.fi].fi+v[e.se].se-v[e.fi].se,e);
    }
    sort(all(ev));
    for(auto&t:ev)
    {
        if(uf.par(t.se.fi)!=uf.par(t.se.se))
            wv.eb(t.fi);
        uf.uni(t.se.fi,t.se.se);
    }
    vector<ll>ps(1,0);
    for(int&t:wv)
        ps.eb(ps.back()+t);
    for(int i=0;i<c;i++)
    {
        int b,h;
        cin>>b>>h;
        if((int)wv.size()+h<n)
        {
            cout<<-1<<'\n';
            continue;
        }
        int pos=max(n-h,(int)(lower_bound(all(wv),b)-wv.begin()));
        cout<<ps[pos]+(ll)(n-pos)*b<<'\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1024 KB Output is correct
2 Correct 172 ms 9832 KB Output is correct
3 Correct 175 ms 10020 KB Output is correct
4 Incorrect 306 ms 17240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1024 KB Output is correct
2 Correct 172 ms 9832 KB Output is correct
3 Correct 175 ms 10020 KB Output is correct
4 Incorrect 306 ms 17240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1024 KB Output is correct
2 Correct 172 ms 9832 KB Output is correct
3 Correct 175 ms 10020 KB Output is correct
4 Incorrect 306 ms 17240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1024 KB Output is correct
2 Correct 172 ms 9832 KB Output is correct
3 Correct 175 ms 10020 KB Output is correct
4 Incorrect 306 ms 17240 KB Output isn't correct
5 Halted 0 ms 0 KB -