Submission #69300

#	Time	Username	Problem	Language	Result	Execution time	Memory
69300		Talant	Port Facility (JOI17_port_facility)	C++17	22 / 100	6012 ms	33316 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 N = (int)1e6 + 5;
const int inf = (int)1e9 + 7;

int n;
int a[N],b[N];
int f[N];
int u[N];
int cn;

vector <vector<int> > g;

bool check(int l,int r) {
      if (a[l] < a[r] && a[r] < b[l] && b[l] < b[r]) return true;
      return false;
}
void dfs (int v,int p = 0,int c = 1) {
      u[v] = 1;
      f[v] = c;

      for (auto to : g[v]) {
            if (!u[to]) dfs(to,v,c + 1);
            if (u[to] == 1 && to != p) {
                  if ((f[to] & 1) != ((c + 1) & 1)) {
                        cout << 0;
                        exit(0);
                  }
            }
      }
      u[v] = 2;
}
int binpow (int a,int b) {
      int res = 1;
      while (b) {
            if (b & 1) res *= a;
            a *= a;
            b /= 2;
            a %= inf;
            res %= inf;
      }
      return (res % inf);
}
main () {
      cin >> n;

      g.resize(n + 1);

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

      for (int i = 1; i <= n; i ++) {
            for (int j = i + 1; j <= n; j ++) {
                  if (check(i,j) || check(j,i)) g[i].pb(j),g[j].pb(i);
            }
      }
      for (int i = 1; i <= n; i ++) {
            if (!u[i]) {
                  cn ++;
                  dfs(i);
            }
      }
      cout << binpow(2,cn) << endl;
}

Compilation message (stderr)

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

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