Submission #383464

#	Time	Username	Problem	Language	Result	Execution time	Memory
383464		mohamedsobhi777	Collapse (JOI18_collapse)	C++14	5 / 100	9411 ms	9836 KiB

collapse

#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 (stderr)

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 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35