oj.uz

Submission #972385

# Submission time Handle Problem Language Result Execution time Memory
972385 2024-04-30T11:36:14 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 15 ms 3164 KB 
#include "rainbow.h"

#include <bits/stdc++.h>

using namespace std;

struct DSU{
   int n;
   vector<int> lab;
   int cc;
   void init(int _n){
      n=_n;
      cc=n;
      lab.assign(n+1, -1);
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   void union_sets(int u, int v){
      u=find_set(u), v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         lab[u]+=lab[v];
         lab[v]=u;
         --cc;
      }
   }
} dsu;

const int dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
bool a[100][100];
int r, c;

void init(int R, int C, int sr, int sc, int M, char *S) {
   r=R, c=C;
   a[sr][sc]=1;
   for (int i=0; i<M; ++i){
      if (S[i]=='N') --sr;
      if (S[i]=='S') ++sr;
      if (S[i]=='E') ++sc;
      if (S[i]=='W') --sc;
      a[sr][sc]=1;
   }
}

int colour(int ar, int ac, int br, int bc) {
   dsu.init((br-ar+1)*(bc-ac+1));
   for (int i=ar; i<=br; ++i) for (int j=ac; j<=bc; ++j){
      if (a[i][j]) --dsu.cc;
      else{
         for (int k=0; k<4; ++k){
            int x=i+dx[k], y=j+dy[k];
            if (x<ar || y<ac || x>br || y>bc || a[x][y]) continue;
            dsu.union_sets((i-ar)*(bc-ac+1)+(j-ac), (x-ar)*(bc-ac+1)+(y-ac));
         }
      }
   }
   return dsu.cc;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 5 ms 500 KB Output is correct
3 Correct 14 ms 348 KB Output is correct
4 Correct 15 ms 344 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 12 ms 348 KB Output is correct
12 Correct 9 ms 348 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 3 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 2 ms 3164 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 5 ms 500 KB Output is correct
3 Correct 14 ms 348 KB Output is correct
4 Correct 15 ms 344 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 12 ms 348 KB Output is correct
12 Correct 9 ms 348 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 3 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Runtime error 1 ms 860 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 5 ms 500 KB Output is correct
3 Correct 14 ms 348 KB Output is correct
4 Correct 15 ms 344 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 12 ms 348 KB Output is correct
12 Correct 9 ms 348 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 3 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Runtime error 1 ms 860 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -