Submission #69287

#	Time	Username	Problem	Language	Result	Execution time	Memory
69287		Talant	Port Facility (JOI17_port_facility)	C++17	10 / 100	3507 ms	1049600 KiB

port_facility

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define Scan(a) scanf ("%I64d", &a)
#define scan(a) scanf ("%d", &a)

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)1e6;

struct node {
      int x,y;
      node() {
            x = y = 0;
      }
};

node a[N];
int n;
int ans;
int u[N];
int f[N];
int cnt;

vector <int> g[N];

bool cmp (node a,node b) {
      return a.x < b.x;
}
bool check (int a,int b,int l,int r) {
      if (a < l && l < b && b < r) return false;
      return true;
}
void bfs (int v) {
      queue<pair<int,int> > q;
      q.push(mk(v,0));

      while (!q.empty()) {
            int v = q.front().fr,c = q.front().sc;

            q.pop();

            u[v] = 1;
            f[v] = c;

            for (auto to : g[v])
                  if (!u[to]) q.push(mk(to,c ^ 1));
                  else if (u[to] && (c ^ 1) != f[to] && f[to] >= 0){
                        cout << 0 << endl;
                        exit(0);
                  }
      }
}
int binpow (int a,int b) {
      int res = 1;
      while (b) {
            if (b & 1) res *= a;
            a *= a;
            b >>= 1;
            a %= inf;
            res %= inf;
      }
      return (res % inf);
}
main () {
      cin >> n;

      for (int i = 1; i <= n; i ++)
            cin >> a[i].x >> a[i].y;

      sort (a + 1,a + n + 1,cmp);

      for (int i = 1; i <= n; i ++) {
            for (int j = i + 1; j <= n; j ++) {
                  if (!check(a[i].x,a[i].y,a[j].x,a[j].y))
                              g[i].pb(j),g[j].pb(i);
            }
            f[i] = -1;
      }
      for (int i = 1; i <= n; i ++) {
            if (!u[i]) {
                  cnt ++;
                  bfs(i);
            }
      }

      cout << binpow (2,cnt) % inf << endl;
}

Compilation message (stderr)

port_facility.cpp:71:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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