oj.uz

답안 #102200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102200 2019-03-23T11:42:21 Z Minnakhmetov Collapse (JOI18_collapse) C++14
0 / 100
 81 ms 4468 KB 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

#include "collapse.h"
using namespace std;

struct E {
	int x, y, i;
	bool operator < (const E &oth) const {
		return x < oth.x;
	}
};

struct Q {
	int t, type, i, x;
	bool operator < (const Q &oth) const {
		return t == oth.t ? type : t < oth.t;
	}
};

const int N = 1e5 + 5, Z = 350;
bool isOn[N], usedv[N], usede[N];
int par[N];
vector<E> edges, se1, se2;
map<pair<int, int>, int> mp_e;
vector<int> ans;
map<int, vector<pair<int, int>>> mp;
int n, m;

#define all(aaa) aaa.begin(), aaa.end()

int findSet(int v) {
	return par[v] == v ? v : par[v] = findSet(par[v]);
}

bool un(int x, int y) {
	x = findSet(x);
	y = findSet(y);
	if (x == y)
		return false;
	if (usedv[y])
		swap(x, y);
	par[y] = x;
	return true;
}

void solve(vector<Q> qr) {
	fill(usedv, usedv + N, false);
	mp.clear();

	vector<Q> s;
	vector<E> ve;
	vector<int> vtx;
	
	for (Q q : qr) {
		if (q.type) {
			usede[q.i] = usedv[edges[q.i].x] = 
				usedv[edges[q.i].y] = 1;
		}
		else {
			s.push_back(q);
		}
	}

	for (int i = 0; i < n; i++) {
		if (usedv[i]) {
			vtx.push_back(i);
		}
	}

	for (int i = 0; i < m; i++) {
		if (usede[i]) {
			ve.push_back(edges[i]);
		}
	}

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

	for (int i = 0; i < n; i++) {
		par[i] = i;
	}

	for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
		while (j < se1.size() && se1[j].x <= s[i].x) {
			if (!usede[se1[j].i] && isOn[se1[j].i])
				r += un(se1[j].x, se1[j].y);
			j++;
		}
		ans[s[i].i] -= r;
		for (int k : vtx) {
			if (k <= s[i].x)
				mp[s[i].i].push_back({ k, findSet(k) });
		}
	}

	for (int i = 0; i < n; i++) {
		par[i] = i;
	}

	for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
		while (j < se2.size() && se2[j].x > s[i].x) {
			if (!usede[se2[j].i] && isOn[se2[j].i])
				r += un(se2[j].x, se2[j].y);
			j++;
		}
		ans[s[i].i] -= r;
		for (int k : vtx) {
			if (k > s[i].x)
				mp[s[i].i].push_back({ k, findSet(k) });
		}
	}

	for (Q q : qr) {
		if (q.type) {
			isOn[q.i] ^= 1;
		}
		else {
			for (auto p : mp[q.i])
				par[p.first] = p.second;
			for (E e : ve) {
				if (isOn[e.i] &&
					(e.x <= q.x || e.y > q.x)) {
					ans[q.i] -= un(e.x, e.y);
				}
			}
		}
	}
}

vector<int> simulateCollapse(
	int _n,
	vector<int> T,
	vector<int> X,
	vector<int> Y,
	vector<int> W,
	vector<int> P
) {
	n = _n;
	m = T.size();
	
	int q = W.size();
	vector<Q> v;

	for (int i = 0; i < m; i++) {
		if (X[i] < Y[i])
			swap(X[i], Y[i]);
		if (!mp_e.count({ X[i], Y[i] })) {
			edges.push_back({ X[i], Y[i], (int)mp_e.size() });
			mp_e[{X[i], Y[i]}] = edges.size() - 1;
		}
		se1.push_back({ X[i], Y[i], i });
		se2.push_back({ Y[i], X[i], i });
		v.push_back({ i, 1, mp_e[{X[i], Y[i]}] });
	}

	sort(all(se1));
	sort(all(se2));
	reverse(all(se2));

	ans.resize(q, _n);

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

	sort(all(v));

	for (int i = 0; i < v.size(); i++) {
		if (i % Z == 0) {
			solve(vector<Q>(v.begin() + i, v.begin() + min((int)v.size(), i + Z)));
		}
	}

	return ans;
}

Compilation message

collapse.cpp: In function 'void solve(std::vector<Q>)':
collapse.cpp:118:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
                                ~~^~~~~~~~~~
collapse.cpp:119:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < se1.size() && se1[j].x <= s[i].x) {
          ~~^~~~~~~~~~~~
collapse.cpp:135:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
                                ~~^~~~~~~~~~
collapse.cpp:136:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < se2.size() && se2[j].x > s[i].x) {
          ~~^~~~~~~~~~~~
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:203:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1152 KB Output is correct
2 Incorrect 7 ms 768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 4460 KB Output is correct
2 Incorrect 68 ms 4468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 4468 KB Output is correct
2 Incorrect 81 ms 4460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1152 KB Output is correct
2 Incorrect 7 ms 768 KB Output isn't correct
3 Halted 0 ms 0 KB -