Submission #810523

#	Time	Username	Problem	Language	Result	Execution time	Memory
810523		thimote75	Port Facility (JOI17_port_facility)	C++14	22 / 100	6067 ms	11068 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

using idata = vector<int>;
using bdata = vector<bool>;
using num = long long;

const int START = 0;
const int END = 1;

const num MOD = 1e9 + 7;

struct Event
{
    int start, end;
    int danger;

    Event() = default;
    Event(int start, int end) : start(start), end(end) {}
};
string to_string (Event event) {
    return to_string(pair<int, int>( event.start, event.end ));
}

struct Time
{
    int time, id;

    int type;

    Time(int time, int id, int type) : time(time), id(id), type(type) {}

    bool operator<(const Time &other)
    {
        return time < other.time;
    }
};

struct UFD
{
    idata parents;
    bdata parity;
    bdata invert;

    UFD(int size)
    {
        parents.resize(size);
        parity .resize(size, false);
        invert .resize(size, false);
        iota(parents.begin(), parents.end(), 0);
    }
    pair<int, bool> compress (int x) {
        if (x == parents[x]) return { x, 0 };

        pair<int, bool> data = compress(parents[x]);
        parents[x] = data.first;
        invert [x] = invert[x] ^ data.second;

        return { parents[x], invert[x] };
    }
    bool getParity (int x) {
        compress(x);
        if (x == parents[x]) return parity[x] ^ invert[x];
        return parity[x] ^ invert[x] ^ invert[parents[x]];
    }
    int boss(int x)
    {
        compress(x);
        return parents[x];
    }
    inline bool isRoot (int node) {
        return parents[node] == node;
    }
    bool merge(int a, int b)
    {
        bool changePar = getParity(a) == getParity(b);
        a = boss(a);
        b = boss(b);
        if (a == b)
            return false;
        
        if (changePar)
            invert [a] = !invert [a];
        parents[a] = b;
        return true;
    }

    int size()
    {
        int res = 0;

        for (int i = 0; i < parents.size(); i++)
            if (isRoot(i))
                res++;

        return res;
    }
};

using vEvent = vector<Event>;
using vTime = vector<Time>;

vEvent events;
vTime timings;

const int MAXLOG = 23;
num pow2(int k)
{
    num table[MAXLOG];
    table[0] = 2;
    for (int i = 1; i < MAXLOG; i++)
        table[i] = (table[i - 1] * table[i - 1]) % MOD;

    num res = 1;
    for (int i = 0; i < MAXLOG; i++)
        if ((1 << i) & k)
            res = (res * table[i]) % MOD;

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    events.resize(N);

    for (int i = 0; i < N; i++)
    {
        int s, e;
        cin >> s >> e;

        events[i] = Event(s, e);

        timings.push_back(Time(s, i, START));
        timings.push_back(Time(e, i, END));
    }

    sort(timings.begin(), timings.end());

    UFD ufd(N);

    set<pair<int, int>> end_values;

    for (Time &time : timings) {
        int timeId   = time.id;
        bool isStart = time.type == START;

        if (!isStart) continue ;

        end_values.insert({ events[timeId].end, timeId });

        auto it = end_values.lower_bound({ events[timeId].end, -1 });
        while (it != end_values.begin()) {
            it --;
            const auto data = *it;

            int currId = data.second;
            if (events[currId].end < events[timeId].start) break ;

            if (ufd.boss(timeId) != ufd.boss(currId))
                ufd.merge(timeId, currId);
        }
    }

    bool valid = true;

    vector<int> A; vector<int> B;
    for (Time &time : timings) {
        int  id   = time.id;
        bool useA = ufd.getParity(id);
        bool isSt = time.type == START;

        vector<int> &C = useA ? A : B;

        if (isSt) C.push_back(id);
        else {
            if (C.back() != id) valid = false;
            C.pop_back();
        } 
    }

    if (valid)
        cout << pow2(ufd.size()) << endl;
    else cout << "0\n";
}

Compilation message (stderr)

port_facility.cpp: In member function 'int UFD::size()':
port_facility.cpp:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (int i = 0; i < parents.size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22