oj.uz

Submission #602379

# Submission time Handle Problem Language Result Execution time Memory
602379 2022-07-23T02:29:24 Z rrrr10000 Fountain Parks (IOI21_parks) C++17
5 / 100
 374 ms 46880 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define fi first
#define se second
#define pb emplace_back
#define all(a) a.begin(),a.end()
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
vi dx={2,0,-2,0},dy={0,2,0,-2};
int construct_roads(std::vector<int> X, std::vector<int> Y) {
    if (X.size() == 1) {
	    build({}, {}, {}, {});
        return 1;
    }
    ll n=X.size();
    map<P,ll> mp;
    rep(i,n)mp[P(X[i],Y[i])]=i;
    vp edge;
    rep(i,n)rep(j,2){
        ll nx=X[i]+dx[j],ny=Y[i]+dy[j];
        if(mp.count(P(nx,ny)))edge.pb(i,mp[P(nx,ny)]);
    }
    {
        vvi g(n);
        for(auto x:edge){
            g[x.fi].pb(x.se);
            g[x.se].pb(x.fi);
        }
        queue<ll> que;
        vb done(n,false);
        done[0]=true;
        que.push(0);
        while(!que.empty()){
            ll t=que.front();que.pop();
            for(ll x:g[t])if(!done[x]){
                done[x]=true;que.push(x);
            }
        }
        rep(i,n)if(!done[i])return 0;
    }
    vector<int> u, v, a, b;
    bool small=true;
    rep(i,n)if(X[i]>6)small=false;
    if(small){
        for(auto x:edge){
            if(X[x.fi]==X[x.se]){
                ll t=X[x.fi];
                if(t==2||t==6){
                    u.pb(x.fi);v.pb(x.se);
                    if(t==2)a.pb(1);
                    else a.pb(7);
                    b.pb((Y[x.fi]+Y[x.se])/2);
                }
                else{
                    if(mp.count(P(t-1,Y[x.fi]))&&mp.count(P(t-1,Y[x.se])))continue;
                    if(mp.count(P(t+1,Y[x.fi]))&&mp.count(P(t+1,Y[x.se])))continue;
                    u.pb(x.fi);v.pb(x.se);
                    a.pb(3);b.pb((Y[x.fi]+Y[x.se])/2);
                }
            }
            else{
                u.pb(x.fi);v.pb(x.se);
                a.pb((X[x.fi]+X[x.se])/2);
                b.pb(Y[x.fi]-1);
            }
        }
        build(u, v, a, b);
        return 1;
    }
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:29:15: warning: control reaches end of non-void function [-Wreturn-type]
   29 |     map<P,ll> mp;
      |               ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 138 ms 16696 KB Output is correct
10 Correct 10 ms 1900 KB Output is correct
11 Correct 58 ms 8716 KB Output is correct
12 Correct 14 ms 2636 KB Output is correct
13 Correct 36 ms 7196 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 149 ms 17144 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 138 ms 16696 KB Output is correct
10 Correct 10 ms 1900 KB Output is correct
11 Correct 58 ms 8716 KB Output is correct
12 Correct 14 ms 2636 KB Output is correct
13 Correct 36 ms 7196 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 149 ms 17144 KB Output is correct
17 Incorrect 1 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 138 ms 16696 KB Output is correct
10 Correct 10 ms 1900 KB Output is correct
11 Correct 58 ms 8716 KB Output is correct
12 Correct 14 ms 2636 KB Output is correct
13 Correct 36 ms 7196 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 149 ms 17144 KB Output is correct
17 Incorrect 1 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 138 ms 16696 KB Output is correct
10 Correct 10 ms 1900 KB Output is correct
11 Correct 58 ms 8716 KB Output is correct
12 Correct 14 ms 2636 KB Output is correct
13 Correct 36 ms 7196 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 149 ms 17144 KB Output is correct
17 Runtime error 1 ms 340 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 138 ms 16696 KB Output is correct
10 Correct 10 ms 1900 KB Output is correct
11 Correct 58 ms 8716 KB Output is correct
12 Correct 14 ms 2636 KB Output is correct
13 Correct 36 ms 7196 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 149 ms 17144 KB Output is correct
17 Runtime error 374 ms 46880 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 138 ms 16696 KB Output is correct
10 Correct 10 ms 1900 KB Output is correct
11 Correct 58 ms 8716 KB Output is correct
12 Correct 14 ms 2636 KB Output is correct
13 Correct 36 ms 7196 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 149 ms 17144 KB Output is correct
17 Incorrect 1 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -