Submission #1100769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100769		lmToT27	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	648 ms	65608 KiB

joitter2

#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
#define ll long long

using namespace std;
namespace std {
	template <typename T, int D>
	struct _vector : public vector <_vector <T, D - 1>> {
		static_assert(D >= 1, "Dimension must be positive!");
		template <typename... Args>
		_vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
	};
	// _vector <int, 3> a(n, m, k);: int a[n][m][k].
	// _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
	template <typename T>
	struct _vector <T, 1> : public vector <T> {
		_vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
	};
}

const int MAX = 1e5 + 3;
const ll MOD[] = {1000000007, 998244353};

int n, m;
int pa[MAX];
ll sz[MAX];
set <int> followers[MAX], in[MAX], out[MAX];
queue <pair <int, int>> toJoin;
ll ans;

int getSize(int i) {
	return followers[i].size() + in[i].size() + out[i].size();
}

void insertOneWay(int u, int v) {
	out[u].insert(v);
	in[v].insert(u);
	if (out[v].count(u)) {
		toJoin.push({u, v});
	}
}

int findpa(int u) {
	return u == pa[u] ? u : pa[u] = findpa(pa[u]);
}

void join(int u, int v) {
	u = findpa(u);
	v = findpa(v);
	if (u == v) return;
	if (getSize(u) < getSize(v)) swap(u, v);
	
	ans += 1ll * sz[u] * followers[v].size() + 1ll * sz[v] * followers[u].size();
	
	pa[v] = u;
	sz[u] += sz[v];
	
	for (int i : followers[v]) {
		if (followers[u].count(i)) ans -= sz[u];
		else followers[u].insert(i);
	}

	in[u].erase(v);
	in[v].erase(u);
	out[u].erase(v);
	out[v].erase(u);

	for (int i : in[v]) {
		out[i].erase(v);
		insertOneWay(i, u);
	}
	
	for (int i : out[v]) {
		in[i].erase(v);
		insertOneWay(u, i);
	}
}

void Solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		pa[i] = i;
		sz[i] = 1;
		followers[i].insert(i);
	}
	int u, v;
	while (m--) {
		cin >> u >> v;
		v = findpa(v);
		if (findpa(u) != v && !followers[v].count(u)) {
			followers[v].insert(u);
			ans += sz[v];
			u = findpa(u);
			insertOneWay(u, v);
			while (toJoin.size()) {
				auto [u, v] = toJoin.front();
				join(u, v);
				toJoin.pop();				
			}
		}
		cout << ans << '\n';
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	#define TASK ""
	if (fopen(TASK".INP", "r")) {
		freopen(TASK".INP", "r", stdin);
		freopen(TASK".OUT", "w", stdout);
	}
	
	if (fopen("TASK.INP", "r")) {
		freopen("TASK.INP", "r", stdin);
		freopen("TASK.OUT", "w", stdout);
	}
	
	/* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();

	cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
	return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int32_t main()':
joitter2.cpp:111:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   freopen(TASK".INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:112:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   freopen(TASK".OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:116:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   freopen("TASK.INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:117:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   freopen("TASK.OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83