oj.uz

Submission #283703

# Submission time Handle Problem Language Result Execution time Memory
283703 2020-08-26T05:49:02 Z 최은수(#5746) 도로 건설 사업 (JOI13_construction) C++17
40 / 100
 5000 ms 22604 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;
    v.insert(v.begin(),v[0]);
    vector<int>sv;
    for(int i=0;i++<n;)
        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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 640 KB Output is correct
2 Correct 176 ms 9332 KB Output is correct
3 Correct 168 ms 9304 KB Output is correct
4 Correct 271 ms 16332 KB Output is correct
5 Correct 158 ms 13656 KB Output is correct
6 Correct 172 ms 10844 KB Output is correct
7 Correct 180 ms 18000 KB Output is correct
8 Correct 160 ms 13912 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 640 KB Output is correct
2 Correct 176 ms 9332 KB Output is correct
3 Correct 168 ms 9304 KB Output is correct
4 Correct 271 ms 16332 KB Output is correct
5 Correct 158 ms 13656 KB Output is correct
6 Correct 172 ms 10844 KB Output is correct
7 Correct 180 ms 18000 KB Output is correct
8 Correct 160 ms 13912 KB Output is correct
9 Correct 2243 ms 11432 KB Output is correct
10 Correct 2261 ms 11480 KB Output is correct
11 Correct 1484 ms 11480 KB Output is correct
12 Correct 1597 ms 11480 KB Output is correct
13 Execution timed out 5061 ms 12372 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 640 KB Output is correct
2 Correct 176 ms 9332 KB Output is correct
3 Correct 168 ms 9304 KB Output is correct
4 Correct 271 ms 16332 KB Output is correct
5 Correct 158 ms 13656 KB Output is correct
6 Correct 172 ms 10844 KB Output is correct
7 Correct 180 ms 18000 KB Output is correct
8 Correct 160 ms 13912 KB Output is correct
9 Correct 400 ms 18376 KB Output is correct
10 Correct 413 ms 18136 KB Output is correct
11 Correct 389 ms 14872 KB Output is correct
12 Correct 459 ms 21780 KB Output is correct
13 Correct 322 ms 10260 KB Output is correct
14 Correct 427 ms 19416 KB Output is correct
15 Correct 430 ms 18008 KB Output is correct
16 Correct 395 ms 17336 KB Output is correct
17 Correct 343 ms 22604 KB Output is correct
18 Correct 383 ms 18520 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 640 KB Output is correct
2 Correct 176 ms 9332 KB Output is correct
3 Correct 168 ms 9304 KB Output is correct
4 Correct 271 ms 16332 KB Output is correct
5 Correct 158 ms 13656 KB Output is correct
6 Correct 172 ms 10844 KB Output is correct
7 Correct 180 ms 18000 KB Output is correct
8 Correct 160 ms 13912 KB Output is correct
9 Correct 2243 ms 11432 KB Output is correct
10 Correct 2261 ms 11480 KB Output is correct
11 Correct 1484 ms 11480 KB Output is correct
12 Correct 1597 ms 11480 KB Output is correct
13 Execution timed out 5061 ms 12372 KB Time limit exceeded
14 Halted 0 ms 0 KB -