oj.uz

Submission #383462

# Submission time Handle Problem Language Result Execution time Memory
383462 2021-03-30T01:13:08 Z mohamedsobhi777 Collapse (JOI18_collapse) C++14
5 / 100
 10376 ms 11372 KB 
#include <bits/stdc++.h>
#include "collapse.h"

using namespace std;

const int N = 5000 + 7;

vector<int> qs[N];
set<int> adj[N];

struct dsu
{
       int fat[N];
       int comp = 0;
       dsu()
       {
              iota(fat, fat + N, 0);
       }
       int find(int x) { return fat[x] = (x == fat[x] ? x : find(fat[x])); }
       void link(int u, int v)
       {
              u = find(u), v = find(v);
              comp += (u != v);
              fat[u] = v;
       }
       bool same(int u, int v)
       {
              return find(u) == find(v);
       }
};

std::vector<int> simulateCollapse(
    int N,
    std::vector<int> T,
    std::vector<int> X,
    std::vector<int> Y,
    std::vector<int> W,
    std::vector<int> P)
{

       vector<int> ret(W.size(), 0);

       for (int i = 0; i < W.size(); ++i)
       {
              qs[W[i]].push_back(i);
       }

       for (int i = 0; i < T.size(); ++i)
       {
              if (T[i] == 0)
              {
                     adj[X[i]].insert(Y[i]);
                     adj[Y[i]].insert(X[i]);
              }
              else
              {
                     adj[X[i]].erase(Y[i]);
                     adj[Y[i]].erase(X[i]);
              }
              for (auto li : qs[i])
              {
                     int ans = 0;
                     dsu d;
                     int x = P[li];

                     for (int j = 0; j < N; ++j)
                     {
                            for (auto u : adj[j])
                            {
                                   if (max(j, u) <= x || min(j, u) >= x + 1)
                                   {
                                          d.link(j, u);
                                   }
                            }
                     }
                     ans = N - d.comp;

                     ret[li] = ans;
              }
       }
       return ret;
}

Compilation message

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |        for (int i = 0; i < W.size(); ++i)
      |                        ~~^~~~~~~~~~
collapse.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |        for (int i = 0; i < T.size(); ++i)
      |                        ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1132 KB Output is correct
2 Correct 15 ms 896 KB Output is correct
3 Correct 16 ms 876 KB Output is correct
4 Correct 18 ms 876 KB Output is correct
5 Correct 20 ms 1132 KB Output is correct
6 Correct 478 ms 1772 KB Output is correct
7 Correct 96 ms 928 KB Output is correct
8 Correct 96 ms 876 KB Output is correct
9 Correct 101 ms 1132 KB Output is correct
10 Correct 213 ms 1260 KB Output is correct
11 Correct 763 ms 1772 KB Output is correct
12 Correct 768 ms 1772 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 3688 KB Output is correct
2 Correct 287 ms 3820 KB Output is correct
3 Runtime error 53 ms 11372 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 3688 KB Output is correct
2 Correct 282 ms 3564 KB Output is correct
3 Correct 295 ms 3948 KB Output is correct
4 Correct 327 ms 3948 KB Output is correct
5 Correct 1267 ms 3948 KB Output is correct
6 Correct 10376 ms 5096 KB Output is correct
7 Runtime error 47 ms 10348 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1132 KB Output is correct
2 Correct 15 ms 896 KB Output is correct
3 Correct 16 ms 876 KB Output is correct
4 Correct 18 ms 876 KB Output is correct
5 Correct 20 ms 1132 KB Output is correct
6 Correct 478 ms 1772 KB Output is correct
7 Correct 96 ms 928 KB Output is correct
8 Correct 96 ms 876 KB Output is correct
9 Correct 101 ms 1132 KB Output is correct
10 Correct 213 ms 1260 KB Output is correct
11 Correct 763 ms 1772 KB Output is correct
12 Correct 768 ms 1772 KB Output is correct
13 Correct 275 ms 3688 KB Output is correct
14 Correct 287 ms 3820 KB Output is correct
15 Runtime error 53 ms 11372 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -