Submission #704506

#	Time	Username	Problem	Language	Result	Execution time	Memory
704506		keta_tsimakuridze	Port Facility (JOI17_port_facility)	C++14	22 / 100	6051 ms	135180 KiB

port_facility

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int p[N], c[N];
set<pair<int,int>> s[N][2];
set<pii> S;
void rem(int x) {
    for(int t = 0; t < 2; t++)
    if(s[x][t].size()) S.erase(*s[x][t].begin());
}
void add(int x) {
    for(int t = 0; t < 2; t++)
    if(s[x][t].size()) S.insert(*s[x][t].begin());
}
void merge(int x, int y) {
    if((int)s[p[x]][1].size() + (int)s[p[x]][0].size() < (int)s[p[y]][1].size() + (int)s[p[y]][0].size()) swap(x, y);
    // c[x] ^ 1 --> c[y]
    if(p[x] == p[y]) assert(0);
    int Y = p[y], X = p[x], T = (c[x] == c[y]);
    for(int t = 0; t < 2; t++) {
        while(s[Y][t].size()) {
            pii x = *s[Y][t].begin();
            p[x.s] = X; c[x.s] = t ^ T;
            s[Y][t].erase(x);
            s[X][t ^ T].insert(x);
        }
    }
}
int l[N], r[N], vis[N];
vector<int> V[N];
void dfs(int u, int c) {

    vis[u] = c;
    for(int i = 0; i < V[u].size(); i++) {
        if(!vis[V[u][i]]) dfs(V[u][i], 3 - c);
        if(vis[V[u][i]] == vis[u]) {
            cout << 0;
            exit(0);
        }
    }
}
void add(int x, int y) {
    V[x].push_back(y);
    V[y].push_back(x);
}
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(l[i] < l[j] && r[i] < r[j] && l[j] < r[i]) add(i, j);
        }
    }
    int ans = 1;
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            dfs(i, 2);
            ans = ans * 2 % mod;
        }
    } cout << ans;
    return 0;
    vector<pair<int,pair<int,int>> > x;
    for(int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        x.push_back({l, {r, i}});
        x.push_back({r, {0, i}});
        s[i][0].insert({r, i});
        p[i] = i;
    }
    sort(x.begin(), x.end());
    vector<int> f(n + 2);
    for(int i = 0; i < x.size(); i++) {
        if(x[i].s.f == 0) {
            int id = x[i].s.s, r = x[i].f;
            rem(p[id]);
            s[p[id]][c[id]].erase({r, id});
            add(p[id]);
            continue;
        }
        int r = x[i].s.f, id = x[i].s.s;
        vector<int> v;
        while(S.size() && (*S.begin()).f < r) {
            pii x = *S.begin();
            v.push_back(x.s);
            if(f[p[x.s]] == i + 1) {
                cout << 0;
                return 0;
            }
            f[p[x.s]] = i + 1;
            S.erase(x);
        }
        for(int i = 0; i < v.size(); i++) rem(p[v[i]]), merge(v[i], id);
        add(p[id]);
    }
    for(int i = 1; i <= n; i++) if(p[i] == i) ans = ans * 2 % mod;
    cout << ans;
/*

4
1 3
2 5
4 8
6 7
*/

}

Compilation message (stderr)

port_facility.cpp: In function 'void dfs(int, int)':
port_facility.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 0; i < x.size(); i++) {
      |                    ~~^~~~~~~~~~
port_facility.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int i = 0; i < v.size(); i++) rem(p[v[i]]), merge(v[i], id);
      |                        ~~^~~~~~~~~~

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