oj.uz

Submission #203001

# Submission time Handle Problem Language Result Execution time Memory
203001 2020-02-19T00:44:14 Z gs18115 timeismoney (balkan11_timeismoney) C++14
50 / 100
 2000 ms 61168 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()
#define semicolon ;
#define ryan bear
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+7;
int pa[205];
int par(int x)
{
    if(pa[x]==-1)
        return x;
    return pa[x]=par(pa[x]);
}
int v,e;
vector<pair<pi,pl> >edges;
inline void sort(const pl&p)
{
    sort(all(edges),[=](pair<pi,pl>&x,pair<pi,pl>&y){return x.se.fi*p.se+x.se.se*p.fi<y.se.fi*p.se+y.se.se*p.fi;});
    return;
}
vector<pi>ae;
pl mst(const pl&p)
{
    sort(p);
    ae.clear();
    fill(pa,pa+v,-1);
    ll ct=0,cc=0;
    for(auto&t:edges)
        if(par(t.fi.fi)!=par(t.fi.se))
            pa[par(t.fi.fi)]=par(t.fi.se),ct+=t.se.fi,cc+=t.se.se,ae.eb(t.fi);
    return pl(ct,cc);
}
ll ans;
pl ai;
void findconvex(pl left,pl right)
{
    pl p(left.fi-right.fi,right.se-left.se);
    pl c=mst(p);
    if(c.fi*c.se<ans)
        ai=p,ans=c.fi*c.se;
    if(c==left||c==right)
        return;
    findconvex(left,c);
    findconvex(c,right);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>v>>e;
    edges.resize(e);
    for(auto&t:edges)
        cin>>t.fi.fi>>t.fi.se>>t.se.fi>>t.se.se;
    pl c1=mst(pl(1,65536));
    pl c2=mst(pl(65536,1));
    if(c1.fi*c1.se<c2.fi*c2.se)
        ans=c1.fi*c1.se,ai=pl(1,65536);
    else
        ans=c2.fi*c2.se,ai=pl(65536,1);
    findconvex(c2,c1);
    pl c=mst(ai);
    cout<<c.fi<<' '<<c.se<<endl;
    for(pi&t:ae)
        cout<<'\n'<<t.fi<<' '<<t.se;
    cout<<endl;
    return 0;
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 252 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Execution timed out 2082 ms 61168 KB Time limit exceeded
5 Execution timed out 2085 ms 12556 KB Time limit exceeded
6 Execution timed out 2059 ms 12232 KB Time limit exceeded
7 Execution timed out 2064 ms 3368 KB Time limit exceeded
8 Execution timed out 2064 ms 1516 KB Time limit exceeded
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 248 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 9 ms 376 KB Output is correct
15 Correct 8 ms 376 KB Output is correct
16 Execution timed out 2060 ms 3296 KB Time limit exceeded
17 Execution timed out 2085 ms 2172 KB Time limit exceeded
18 Execution timed out 2047 ms 3192 KB Time limit exceeded
19 Execution timed out 2063 ms 1544 KB Time limit exceeded
20 Execution timed out 2084 ms 1372 KB Time limit exceeded