Submission #69266

#	Time	Username	Problem	Language	Result	Execution time	Memory
69266		Talant	Port Facility (JOI17_port_facility)	C++17	0 / 100	46 ms	47352 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)
#define int long long

using namespace std;

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

struct node {
      int x,y;
};

node a[N];
int n;
int ans;
int u[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 dfs (int v,int p = 0,int c = 1) {
      u[v] = 1;
      for (auto to : g[v]) {
            if (p == to) continue;
            if (!u[to]) dfs(to,v,c + 1);
            else if (u[to] == 1 && (c & 1)) {
                  cout << 0 << endl;
                  exit(0);
            }
      }
      u[v] = 2;
}
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);
            }
      }
      for (int i = 1; i <= n; i ++) {
            if (!u[i]) {
                  cnt ++;
                  dfs(i);
            }
      }

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

Compilation message (stderr)

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

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