oj.uz

Submission #1070405

# Submission time Handle Problem Language Result Execution time Memory
1070405 2024-08-22T14:00:04 Z Arapak Fountain Parks (IOI21_parks) C++17
0 / 100
 1 ms 348 KB 
#include "parks.h"
#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

#ifdef DEBUG
auto& operator<<(auto &os, const pair<auto,auto> &p) {
    return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto &os, const auto &v) {
    os<<"{";
    for(auto it=begin(v);it!=end(v);++it) {
        if(it != begin(v)) os<<", ";
        os<<(*it);
    }
    return os<<"}";
}

void dbg_out(auto... x) {
    ((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif

struct Fountain {
    int x, y, index;

    friend bool operator<(const Fountain &a, const Fountain &b) {
        return tie(a.x, a.y) < tie(b.x, b.y);
    }
};

struct Bench {
    int a, b;
    int x, y;

    friend bool operator<(const Bench &a, const Bench &b) {
        return tie(a.x, a.y) < tie(b.x, b.y);
    }
};

void build_from_benches(set<Bench> &benches) {
    vi u, v, a, b;
    for(auto bench : benches) {
        u.push_back(bench.a);
        v.push_back(bench.b);
        a.push_back(bench.x);
        b.push_back(bench.y);
    }
    build(u, v, a, b);
}

int construct_roads(vi x, vi y) {
    int n = sz(x);
    dbg(x, y);
    set<Fountain> s;
    rep(i,0,n) s.insert({x[i], y[i], i});
    set<Bench> benches;
    for(auto f : s) {
        {
            auto it = s.find({f.x - 2, f.y, -1});
            if(it != s.end()) {
                auto t = *it;
                Bench b;
                b.a = f.index;
                b.b = t.index;
                b.x = f.x - 1;

                b.y = f.y - 1;
                if(benches.count(b))
                    b.y = f.y + 1;
                if(benches.count(b))
                    return 0;
                benches.insert(b);
            }
        }

        {
            auto it = s.find({f.x, f.y - 2, -1});
            if(it != s.end()) {
                auto t = *it;
                Bench b;
                b.a = f.index;
                b.b = t.index;
                b.y = f.y - 1;

                b.x = f.x - 1;
                if(benches.count(b))
                    b.x = f.x + 1;
                if(benches.count(b))
                    return 0;
                benches.insert(b);
            }
        }
    }
    build_from_benches(benches);
    return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -