oj.uz

Submission #383463

# Submission time Handle Problem Language Result Execution time Memory
383463 2021-03-30T01:25:01 Z mohamedsobhi777 Collapse (JOI18_collapse) C++14
0 / 100
 277 ms 10092 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(j > u)continue; 
                                   if (max(j, u) <= x || min(j, u) >= x + 1)
                                   {

                                          assert(!d.same(j , u)) ;
                                          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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1132 KB Output is correct
2 Runtime error 10 ms 1516 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 3324 KB Output is correct
2 Correct 277 ms 3388 KB Output is correct
3 Runtime error 58 ms 10092 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 277 ms 3304 KB Output is correct
2 Runtime error 132 ms 6252 KB Execution killed with signal 6
3 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 Runtime error 10 ms 1516 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -