제출 #1172664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172664		nuutsnoynton	Topovi (COCI15_topovi)	C++20	120 / 120	869 ms	39884 KiB

topovi

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

map < ll, ll > mur_xor, bagana_xor;
map < ll, ll > mur_xor_cnt, bagana_xor_cnt;
map < pair < ll, ll > , ll > val;
ll F(ll x, ll y) {
	return x * y;
}
ll S(ll x, ll y) {
	return x + y;
}
int main() {
	ll n, m, r, x, y, i, j, ans, t, N, K, murxor, baganaxor, value, P, x1, y1, x2, y2, c;

	cin >> N >> K >> P;
	
	mur_xor_cnt[0] = N;
	bagana_xor_cnt[0] = N;
	for (i = 1; i <= K; i ++) {
		cin >> x1 >> y1 >> c;
		val[make_pair(x1, y1)] = c;
		mur_xor_cnt[mur_xor[x1]] --;
		bagana_xor_cnt[bagana_xor[y1]] --;
		mur_xor[x1] ^= c;
		bagana_xor[y1] ^= c;
		mur_xor_cnt[mur_xor[x1]] ++;
		bagana_xor_cnt[bagana_xor[y1]] ++;
	}
	ans = N * N;
	
	for (auto R : mur_xor_cnt) {
		ans = ans - F(R.second, bagana_xor_cnt[R.first]);
	//	cout << R.first << " " << R.second << " " << ans << endl;
	}
//	for (auto R : bagana_xor_cnt) {
//		ans = ans - min(R.second, mur_xor_cnt[R.first]);
//	}
	//cout << ans <<"RR" <<endl;
	for (i = 1; i <= P; i ++) {
		cin >> x1 >> y1 >> x2 >> y2;
		value = val[make_pair(x1, y1)];
		murxor = mur_xor[x1];
		baganaxor = bagana_xor[y1];
	//	if ( murxor == baganaxor) ans --;
		mur_xor_cnt[mur_xor[x1]] --;
		bagana_xor_cnt[bagana_xor[y1]] --;
		ans = ans + S(mur_xor_cnt[baganaxor], bagana_xor_cnt[murxor]);
		
	//	if ( murxor == baganaxor) ans --;
	//	if (murxor != baganaxor) ans = ans + S(mur_xor_cnt[baganaxor], bagana_xor_cnt[baganaxor]);
	//	cout << ans << " ";
		
		mur_xor[x1] ^= value;
		bagana_xor[y1] ^= value;
		murxor = mur_xor[x1];
		baganaxor = bagana_xor[y1];
		
	//	if ( murxor == baganaxor) ans ++;
		
		ans = ans - S(mur_xor_cnt[baganaxor], bagana_xor_cnt[murxor]);
		mur_xor_cnt[mur_xor[x1]] ++;
		bagana_xor_cnt[bagana_xor[y1]] ++;
		val[make_pair(x1, y1)] = 0;
	//	if ( murxor == baganaxor) ans --;
	//	if (murxor != baganaxor) ans = ans - S(mur_xor_cnt[baganaxor], bagana_xor_cnt[baganaxor]);
	//	cout << ans << " ";
		murxor = mur_xor[x2];
		baganaxor = bagana_xor[y2];
	//	if ( murxor == baganaxor) ans --;
		mur_xor_cnt[mur_xor[x2]] --;
		bagana_xor_cnt[bagana_xor[y2]] --;
		ans = ans + S(mur_xor_cnt[baganaxor], bagana_xor_cnt[murxor]);
		
	//	if ( murxor == baganaxor) ans ++;
	//	if (murxor != baganaxor) ans = ans + S(mur_xor_cnt[baganaxor], bagana_xor_cnt[baganaxor]);
	//	cout << ans << " ";
		
		mur_xor[x2] ^= value;
		bagana_xor[y2] ^= value;
		val[make_pair(x2, y2)] = value;
		
		murxor = mur_xor[x2];
		baganaxor = bagana_xor[y2];
	//	if ( murxor == baganaxor) ans ++;
		ans = ans - S(mur_xor_cnt[baganaxor], bagana_xor_cnt[murxor]);
		mur_xor_cnt[mur_xor[x2]] ++;
		bagana_xor_cnt[bagana_xor[y2]] ++;
	//	if ( murxor == baganaxor) ans --;
	//	if (murxor != baganaxor) ans = ans - S(mur_xor_cnt[baganaxor], bagana_xor_cnt[baganaxor]);
		cout << ans << "\n";
	}
	
	
}

• Subtask 1: 120 / 120