oj.uz

Submission #70481

# Submission time Handle Problem Language Result Execution time Memory
70481 2018-08-23T04:17:25 Z funcsr Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 392 ms 70164 KB 
#include "rainbow.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct UF {
  vector<int> U, R;
  int C;
  UF(int N) {
    rep(i, N) U.pb(i), R.pb(1);
    C = N;
  }
  int find(int x) {
    if (U[x]==x)return x;
    return U[x]=find(U[x]);
  }
  void unite(int x, int y) {
    x=find(x), y=find(y);
    if (x==y)return;
    if (R[x]<R[y])swap(x,y);
    U[y]=x;
    R[x]+=R[y];
    C--;
  }
};
int H, W;
bool bad[50][50];
int id[50][50];
vector<int> both[4], both2[4];
bool yo[4][200000];

void init(int HH, int WW, int sr, int sc, int M, char *S) {
  H = HH, W = WW;
  if (H == 2) {
    map<P, bool> bad;
    int y = sr-1, x = sc-1;
    bad[P(x, y)] = true;
    rep(i, M) {
      if (S[i] == 'N') y--;
      if (S[i] == 'S') y++;
      if (S[i] == 'W') x--;
      if (S[i] == 'E') x++;
      bad[P(x, y)] = true;
    }
    rep(S, 1<<H) {
      rep(x, W) {
        bool all = true;
        rep(y, H) if ((S>>y)&1 && !bad[P(x,y)]) all = false;
        yo[S][x] = all;
      }
      rep(x, W) if (yo[S][x]) both[S].pb(x);
      rep(x, W-1) if (yo[S][x]&&yo[S][x+1]) both2[S].pb(x);
    }
  }
  else if (W <= 50 && H <= 50) {
    int y = sr-1, x = sc-1;
    bad[x][y] = true;
    rep(i, M) {
      if (S[i] == 'N') y--;
      if (S[i] == 'S') y++;
      if (S[i] == 'W') x--;
      if (S[i] == 'E') x++;
      bad[x][y] = true;
    }
  }
  else abort();
}

int colour(int ar, int ac, int br, int bc) {
  ar--, ac--, br--, bc--;
  if (H == 2) {
    int S = 0;
    for (int y=ar; y<=br; y++) S |= 1<<y;
    int l = ac, r = bc;
    int s = index(both[S], r+1)-index(both[S], l);
    if (s==0)return 1;
    s -= index(both2[S], r)-index(both2[S], l);
    s++;
    if (yo[S][l]) s--;
    if (yo[S][r]) s--;
    return s;
  }
  else if (W <= 50 && H <= 50) {
    int V = 0;
    for (int x=ac; x<=bc; x++) {
      for (int y=ar; y<=br; y++) {
        if (!bad[x][y]) id[x][y] = V++;
        else id[x][y] = -1;
      }
    }
    UF uf(V);
    for (int x=ac; x<=bc; x++) {
      for (int y=ar; y<=br; y++) {
        if (x+1<=bc && !bad[x][y] && !bad[x+1][y]) uf.unite(id[x][y], id[x+1][y]);
        if (y+1<=br && !bad[x][y] && !bad[x][y+1]) uf.unite(id[x][y], id[x][y+1]);
      }
    }
    return uf.C;
  }
  else abort();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 12 ms 516 KB Output is correct
3 Correct 31 ms 800 KB Output is correct
4 Correct 28 ms 828 KB Output is correct
5 Correct 10 ms 828 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 4 ms 836 KB Output is correct
8 Correct 2 ms 884 KB Output is correct
9 Correct 2 ms 900 KB Output is correct
10 Correct 3 ms 1028 KB Output is correct
11 Correct 31 ms 1028 KB Output is correct
12 Correct 23 ms 1072 KB Output is correct
13 Correct 15 ms 1092 KB Output is correct
14 Correct 9 ms 1192 KB Output is correct
15 Correct 2 ms 1192 KB Output is correct
16 Correct 2 ms 1192 KB Output is correct
17 Correct 2 ms 1192 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1192 KB Output is correct
2 Correct 2 ms 1192 KB Output is correct
3 Correct 330 ms 32968 KB Output is correct
4 Correct 392 ms 36116 KB Output is correct
5 Correct 381 ms 38864 KB Output is correct
6 Correct 361 ms 41756 KB Output is correct
7 Correct 358 ms 44552 KB Output is correct
8 Correct 306 ms 46584 KB Output is correct
9 Correct 341 ms 50552 KB Output is correct
10 Correct 356 ms 53420 KB Output is correct
11 Correct 333 ms 56436 KB Output is correct
12 Correct 307 ms 58964 KB Output is correct
13 Correct 327 ms 61892 KB Output is correct
14 Correct 315 ms 64752 KB Output is correct
15 Correct 325 ms 67824 KB Output is correct
16 Correct 354 ms 70164 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1192 KB Output is correct
2 Runtime error 4 ms 70164 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 12 ms 516 KB Output is correct
3 Correct 31 ms 800 KB Output is correct
4 Correct 28 ms 828 KB Output is correct
5 Correct 10 ms 828 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 4 ms 836 KB Output is correct
8 Correct 2 ms 884 KB Output is correct
9 Correct 2 ms 900 KB Output is correct
10 Correct 3 ms 1028 KB Output is correct
11 Correct 31 ms 1028 KB Output is correct
12 Correct 23 ms 1072 KB Output is correct
13 Correct 15 ms 1092 KB Output is correct
14 Correct 9 ms 1192 KB Output is correct
15 Correct 2 ms 1192 KB Output is correct
16 Correct 2 ms 1192 KB Output is correct
17 Correct 2 ms 1192 KB Output is correct
18 Runtime error 3 ms 70164 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 12 ms 516 KB Output is correct
3 Correct 31 ms 800 KB Output is correct
4 Correct 28 ms 828 KB Output is correct
5 Correct 10 ms 828 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 4 ms 836 KB Output is correct
8 Correct 2 ms 884 KB Output is correct
9 Correct 2 ms 900 KB Output is correct
10 Correct 3 ms 1028 KB Output is correct
11 Correct 31 ms 1028 KB Output is correct
12 Correct 23 ms 1072 KB Output is correct
13 Correct 15 ms 1092 KB Output is correct
14 Correct 9 ms 1192 KB Output is correct
15 Correct 2 ms 1192 KB Output is correct
16 Correct 2 ms 1192 KB Output is correct
17 Correct 2 ms 1192 KB Output is correct
18 Runtime error 3 ms 70164 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -