oj.uz

Submission #383464

# Submission time Handle Problem Language Result Execution time Memory
383464 2021-03-30T01:26:09 Z mohamedsobhi777 Collapse (JOI18_collapse) C++14
5 / 100
 9411 ms 9836 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1004 KB Output is correct
2 Correct 29 ms 876 KB Output is correct
3 Correct 29 ms 876 KB Output is correct
4 Correct 32 ms 876 KB Output is correct
5 Correct 33 ms 1132 KB Output is correct
6 Correct 436 ms 1516 KB Output is correct
7 Correct 101 ms 876 KB Output is correct
8 Correct 101 ms 1004 KB Output is correct
9 Correct 105 ms 1004 KB Output is correct
10 Correct 198 ms 1132 KB Output is correct
11 Correct 632 ms 1476 KB Output is correct
12 Correct 653 ms 1516 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 3304 KB Output is correct
2 Correct 590 ms 3308 KB Output is correct
3 Runtime error 51 ms 9836 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 561 ms 3304 KB Output is correct
2 Correct 556 ms 3308 KB Output is correct
3 Correct 580 ms 3308 KB Output is correct
4 Correct 596 ms 3460 KB Output is correct
5 Correct 1339 ms 3180 KB Output is correct
6 Correct 9411 ms 4252 KB Output is correct
7 Runtime error 49 ms 8684 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 31 ms 1004 KB Output is correct
2 Correct 29 ms 876 KB Output is correct
3 Correct 29 ms 876 KB Output is correct
4 Correct 32 ms 876 KB Output is correct
5 Correct 33 ms 1132 KB Output is correct
6 Correct 436 ms 1516 KB Output is correct
7 Correct 101 ms 876 KB Output is correct
8 Correct 101 ms 1004 KB Output is correct
9 Correct 105 ms 1004 KB Output is correct
10 Correct 198 ms 1132 KB Output is correct
11 Correct 632 ms 1476 KB Output is correct
12 Correct 653 ms 1516 KB Output is correct
13 Correct 554 ms 3304 KB Output is correct
14 Correct 590 ms 3308 KB Output is correct
15 Runtime error 51 ms 9836 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -