oj.uz

Submission #624568

# Submission time Handle Problem Language Result Execution time Memory
624568 2022-08-08T13:27:54 Z Vladth11 Roads (CEOI20_roads) C++14
15 / 100
 581 ms 58940 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
 
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
 
const ll NMAX = 100001;
const ll VMAX = 101;
const ll INF = 1e9;
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 117;
const ll nr_of_bits = 18;
const ll inv2 = 500000004;
 
set <pii> exista;
 
struct event {
    pii x;
    int stare;
    bool operator < (const event a) {
        if(a.x.first != x.first) {
            return x.first < a.x.first;
        }
        if(a.stare != stare) {
            return stare > a.stare;
        }
        return x.second < a.x.second; /// Nu ar trb sa aiba importanta, dar e necesar sa nu busesc sortarea
    }
};
 
int swipex;
 
struct segment {
    int a, b, c, d;
    int idx;
    long double gety() {
        if(c != a)
            return (long double)b + (long double)(swipex - a) * (long double)(d - b) / (long double)(c - a);
        else
            return (long double)b;
    }
} sgt[NMAX];
 
vector <event> events;
map <pii, pii> mp;
set <pii> already;
 
bool signs(int a, int b) {
    if(a < b)
        swap(a, b);
    if(a > 0 && b < 0)
        return 0;
    return 1;
}
 
int cnt = 0;
 
void adauga(int a, int b) {
    if(a < b)
        swap(a, b);
    cnt++;
    if(already.find({a, b}) != already.end()) return;
    already.insert({a, b});
    segment first = sgt[a];
    segment second = sgt[b];
    if(first.b < second.b) {
        swap(first, second);
    } else if(first.b == second.b) {
        if(first.a < second.a) {
            swap(first, second);
        }
    }
    if(first.a >= second.c) {
        cout << first.a << " " << first.b << " " << second.c << " " << second.d << "\n";
        return;
    }
    if(second.a >= first.c) {
        cout << first.c << " " << first.d << " " << second.a << " " << second.b << "\n";
        return;
    }
    cout << first.a << " " << first.b << " " << second.a << " " << second.b << "\n";
}
 
struct ura {
    int first, second;
    bool operator < (const ura a)const {
        if(a.second == -1 && second == -1) {
            return first < a.first;
        }
        if(a.second == -1) {
            return sgt[second].gety() < a.first;
        }
        if(second == -1) {
            return first < sgt[a.second].gety();
        }
        return sgt[second].gety() < sgt[a.second].gety();
    }
};
 
int main() {
    //ifstream cin(".out");
    //ofstream cout(".out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i;
    cin >> n;
    for(i = 1; i <= n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if(a > c) {
            swap(b, d);
            swap(a, c);
        } else if(a == c) {
            if(b > d)
                swap(b, d); /// nu stiu daca e nevoie
        }
        sgt[i] = {a, b, c, d, i};
        exista.insert({a, b});
        exista.insert({c, d});
        events.push_back({{a, b}, i});
        events.push_back({{c, d}, -i});
    }
    n += 2;
    sgt[n - 1] = {-INF, -INF, INF, -INF, n - 1};
    events.push_back({{-INF, -INF}, n - 1});
    events.push_back({{INF, -INF}, -(n - 1)});
    sgt[n] = {-INF, INF, INF, INF, n};
    events.push_back({{-INF, INF}, n});
    events.push_back({{INF, INF}, -n});
    sort(events.begin(), events.end());
    set <ura> active;
    vector <pair <pii, int> > facut;
    vector <pii> tobe;
    for(int i = 0; i < events.size(); i++) {
        swipex = events[i].x.first;
        if(events[i].stare > 0) {
            if(events[i].x.first != -INF) {
                facut.push_back({events[i].x, events[i].stare});
                tobe.push_back({events[i].x.second, events[i].stare});
            } else {
                active.insert({events[i].x.second, events[i].stare});
            }
        } else {
            if(-events[i].stare < n - 1) {
                auto sus = active.lower_bound({sgt[-events[i].stare].gety(), -1});
                sus = prev(sus);
                auto jos = active.lower_bound({sgt[-events[i].stare].gety(), -1});
                jos = next(jos);
                int indS = (*sus).second;
                int indJ = (*jos).second;
                if(mp.find({indS, indJ}) != mp.end())
                    mp[ {indS, indJ}] = max(mp[ {indS, indJ}], {events[i].x.first, -events[i].stare});
                else
                    mp[ {indS, indJ}] = {events[i].x.first, -events[i].stare};
            }
            active.erase({events[i].x.second, -events[i].stare});
        }
        if(i == events.size() || (events[i + 1].x.first != events[i].x.first || !signs(events[i + 1].stare, events[i].stare))) {
            int cc = 0;
            if(facut.size() == 0) continue;
            for(auto x : facut) {
                cc++;
                /// pe primul vrem sa-l conectam la alea din spate
                if(cc == 1) {
                    active.insert({tobe[0].first, tobe[0].second});
                }
                auto sus = active.lower_bound({x.first.second, -1});
                sus = prev(sus);
                auto jos = active.lower_bound({x.first.second, -1}); /// nu vrem daca trece chiar la limita sa-l ignor
                jos = next(jos);
                int indS = (*sus).second;
                int indJ = (*jos).second;
                if(mp.find({indS, indJ}) == mp.end()) {
                    if(sgt[indS].a > sgt[indJ].a) {
                        adauga(indS, x.second);
                    } else if(sgt[indJ].a != -INF) {
                        adauga(indJ, x.second);
                    }
                } else {
                    pii conectare = mp[ {indS, indJ}];
                    adauga(conectare.second, x.second);
                }
                if(cc == 1) {
                    for(auto x : tobe) {
                        active.insert({x.first, x.second});
                    }
                }
                /// Desi il conectam in urma, vrem ca atunci cand e inserat sa tina cont si de ceilalti
                sus = active.lower_bound({x.first.second, -1});
                sus = prev(sus);
                jos = active.lower_bound({x.first.second, -1}); /// nu vrem daca trece chiar la limita sa-l ignor
                jos = next(jos);
                indS = (*sus).second;
                indJ = (*jos).second;
                if(mp.find({indS, indJ}) != mp.end())
                    mp[ {indS, indJ}] = max(mp[ {indS, indJ}], {x.first.first, x.second});
                else
                    mp[ {indS, indJ}] = {x.first.first, x.second};
            }
            tobe.clear();
            facut.clear();
        }
    }
    assert(cnt == n - 3);
    return 0;
 
}

Compilation message

roads.cpp: In function 'int main()':
roads.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(int i = 0; i < events.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
roads.cpp:149:74: warning: narrowing conversion of 'sgt[(- events.std::vector<event>::operator[](((std::vector<event>::size_type)i)).event::stare)].segment::gety()' from 'long double' to 'int' [-Wnarrowing]
  149 |                 auto sus = active.lower_bound({sgt[-events[i].stare].gety(), -1});
      |                                                ~~~~~~~~~~~~~~~~~~~~~~~~~~^~
roads.cpp:151:74: warning: narrowing conversion of 'sgt[(- events.std::vector<event>::operator[](((std::vector<event>::size_type)i)).event::stare)].segment::gety()' from 'long double' to 'int' [-Wnarrowing]
  151 |                 auto jos = active.lower_bound({sgt[-events[i].stare].gety(), -1});
      |                                                ~~~~~~~~~~~~~~~~~~~~~~~~~~^~
roads.cpp:162:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         if(i == events.size() || (events[i + 1].x.first != events[i].x.first || !signs(events[i + 1].stare, events[i].stare))) {
      |            ~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 157 ms 10612 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 21 ms 2452 KB Output is correct
5 Correct 42 ms 4604 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 21 ms 2420 KB Output is correct
5 Correct 54 ms 4544 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 33 ms 3200 KB Output is correct
10 Runtime error 564 ms 58940 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 18 ms 2452 KB Output is correct
5 Correct 41 ms 4576 KB Output is correct
6 Failed 0 ms 212 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
7 Halted 0 ms 0 KB -

Subtask #5
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 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 19 ms 2456 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 29 ms 3196 KB Output is correct
10 Failed 0 ms 212 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
11 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 164 ms 10620 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 25 ms 2484 KB Output is correct
7 Correct 48 ms 4560 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 31 ms 3216 KB Output is correct
12 Runtime error 581 ms 58692 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -