Submission #129255

#	Time	Username	Problem	Language	Result	Execution time	Memory
129255		combi1k1	Collapse (JOI18_collapse)	C++14	100 / 100	4649 ms	22008 KiB

collapse

#include<bits/stdc++.h>

using namespace std;

const int   N   = 1e5 + 5;
const int   B   = 350;

#define all(x)  x.begin(),x.end()
#define sz(x)   x.size()
#define X       first
#define Y       second

typedef pair<int,int>   ii;
typedef vector<int>     vi;

struct Edge {
	int x, y, i;
	bool operator < (const Edge &a) const   {
        return x < a.x;
	}
};
struct Ques {
    int day, typ;
    int idx, ver;
    bool operator < (const Ques &a) const   {
        return  day == a.day ? typ : day < a.day;
    }
};

bool On[N], uV[N], uE[N];

namespace DSU   {
    int p[N];
    int lead(int x) {
        return  p[x] == x ? x : p[x] = lead(p[x]);
    }
    int join(int x,int y)   {
        x = lead(x);
        y = lead(y);
        if (x == y) return  0;
        if (uV[y])  swap(x,y);
        p[y] = x;
        return  1;
    }
};

vector<Edge>    E, se1, se2;
vector<int>     ans;
int n, m;

void calc(vector<Ques>  qr) {
	fill(uV,uV + N,0);
	fill(uE,uE + N,0);

    map<int,vector<ii>> mp;

    vector<Ques>    Q;
    vector<Edge>    ed;
    vector<int>     vx;

    for(Ques q : qr)    {
        if (q.typ)  uE[q.idx] = uV[E[q.idx].x] = uV[E[q.idx].y] = 1;
		else        Q.push_back(q);
	}

	for(int i = 0 ; i < n ; ++i)    if (uV[i])  vx.push_back(i);
	for(int i = 0 ; i < m ; ++i)    if (uE[i])  ed.push_back(E[i]);

    sort(all(Q),[](Ques &a,Ques &b) {
         return  a.ver < b.ver;
    });

    for(int t = 0 ; t < 2 ; ++t)    {
        iota(DSU::p,DSU::p + n,0);
        for(int i = 0, j = 0, r = 0 ; i < sz(Q) ; ++i)   {
            while (j < se1.size())  {
                if (t == 0 && se1[j].x >  Q[i].ver) break;
                if (t == 1 && se1[j].x <= Q[i].ver) break;
                if (!uE[se1[j].i] && On[se1[j].i])
                    r += DSU::join(se1[j].x,se1[j].y);
                j++;
            }
            ans[Q[i].idx] -= r;
            for(int x : vx) {
                if (t == 0 && x >  Q[i].ver)    continue;
                if (t == 1 && x <= Q[i].ver)    continue;
                mp[Q[i].idx].push_back({x,DSU::lead(x)});
            }
        }
        reverse(Q.begin(),Q.end());
        swap(se1,se2);
    }

    for(Ques q : qr)    {
        if (q.typ)  On[q.idx] ^= 1;
        else    {
            for(ii t : mp[q.idx])   DSU::p[t.X] = t.Y;
            for(Edge e : ed)
                if (On[e.i] && (e.x <= q.ver || e.y > q.ver))
                    ans[q.idx] -= DSU::join(e.x,e.y);
        }
	}
}

vi  simulateCollapse(int _,vi T,vi X,vi Y,vi W,vi P)    {
    n = _;
	m = T.size();

	vector<Ques>   v;
	map<ii,int> mp;

	for(int i = 0 ; i < m ; i++)    {
		if (X[i] < Y[i])    swap(X[i], Y[i]);
        int num;
		if(!mp.count({X[i],Y[i]}))  {
            mp[{X[i],Y[i]}] = num = sz(E);
			se1.push_back({X[i],Y[i],num});
			se2.push_back({Y[i],X[i],num});
			E.push_back({X[i],Y[i],num});
		}
		else    num = mp[{X[i],Y[i]}];
		v.push_back({i,1,num,0});
	}
	sort(all(se1));
	sort(all(se2)); reverse(all(se2));

	ans.assign(W.size(),n);

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

	sort(all(v));

	for(int i = 0 ; i < v.size() ; i += B)
        calc(vector<Ques>(v.begin() + i,v.begin() + min((int)v.size(),i + B)));

	return ans;
}

Compilation message (stderr)

collapse.cpp: In function 'void calc(std::vector<Ques>)':
collapse.cpp:75:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0, j = 0, r = 0 ; i < sz(Q) ; ++i)   {
                                         ^
collapse.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (j < se1.size())  {
                    ~~^~~~~~~~~~~~
collapse.cpp: In function 'vi simulateCollapse(int, vi, vi, vi, vi, vi)':
collapse.cpp:129:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < W.size() ; ++i)
                     ~~^~~~~~~~~~
collapse.cpp:129:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i = 0 ; i < W.size() ; ++i)
     ^~~
collapse.cpp:132:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  sort(all(v));
  ^~~~
collapse.cpp:134:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < v.size() ; i += B)
                  ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35