QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#590365	#7181. Graph Cuts	Tomorrow	TL	3815ms	19636kb	C++17	3.1kb	2024-09-25 23:35:58	2024-09-25 23:35:58

Judging History

你现在查看的是最新测评结果

[2024-09-25 23:35:58]
评测

测评结果：TL
用时：3815ms
内存：19636kb

查看

[2024-09-25 23:35:58]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define C const
#define U unsigned
#define SC static
#define CE constexpr
#define TL template
#define TN typename
#define OP operator
#define pb push_back
#define ft first
#define sd second
#define mi (l + (r - l) / 2)
#define TTT TL<TN T = I>
#define TTI TL<TN It>
#define BE(v) v.begin(), v.end()
#define VD void
#define BL bool
#define CH char
#define I int
#define LL long long
#define II __int128
#define D double
#define STR string
using PII = pair<I, I>;
TTT using V = vector<T>;

#define FORX(v) for(auto& x : v)
#define FOR(i, b, e)  for(auto i = b, _e = (decltype(i))e;i != _e; ++i)
#define FORR(i, b, e) for(auto i = b, _e = (decltype(i))e;i != _e; --i)
#define FORV(v, i) for (I i = 0, _n = v.size(), x = _n ? v[0] : 0;i < _n;x = v[++i])
#define FUNC(T, f, ...) function<T(__VA_ARGS__)> f = [&](__VA_ARGS__)->T

#define DR(T, ...) T __VA_ARGS__; R(__VA_ARGS__);
TTT VD R(T& x) { cin >> x; }
TTT T R() { DR(T, x); return x; }
TL<TN T, TN... A> VD R(T& x, A&... a) { R(x), R(a...); }
CE CH LF = '\n', SP = ' ';
TL<CH s = LF> VD W() { cout << s; }
TL<CH s = LF, TN T> VD W(C T& x) { cout << x << s; }
TL<CH s = LF, TN T, TN... A> VD W(C T& x, C A&... a) { W<SP>(x), W<s>(a...); }

TTT CE T inf() { return numeric_limits<T>::max() / 2; }
TTT VD setmin(T& a, C T& b) { if (b < a)a = b; }
TTT VD setmax(T& a, C T& b) { if (a < b)a = b; }

TL<> struct std::hash<PII> { size_t OP()(C PII& p)C{ return (((size_t)p.ft) << 32) | p.sd; } };
VD test()
{
	DR(I, n, m);++n; I sqm = sqrt(m);
	V<I> dg(n), ish(n), vh;
	unordered_map<PII, I> eg;
	V<unordered_map<I, I>> l(n);
	V<unordered_set<I>> s(n), d(n);
	unordered_set<PII> lde;

	FUNC(PII, make, I u, I v) { return u < v ? PII{ u, v } : PII{ v, u }; };
	FOR(i, 0, m) { DR(I, u, v);eg[make(u, v)] = i + 1;++dg[u], ++dg[v]; }
	FOR(i, 1, n)if (dg[i] >= sqm)ish[i] = 1, vh.pb(i);

	FORX(eg)
	{
		I u = x.ft.ft, v = x.ft.sd;
		if (ish[u])s[u].insert(v);
		if (ish[v])s[v].insert(u);
		if (!ish[u] && !ish[v])l[u][v], l[v][u];
	}

	DR(I, q);
	while (q--)
	{
		DR(STR, op);
		if (op[0] != '?')
		{
			DR(I, p);
			if (!ish[p])
			{
				FORX(l[p])
				{
					l[x.ft][p] ^= 1; x.sd ^= 1;
					if (x.sd)lde.insert(make(p, x.ft));
					else lde.erase(make(p, x.ft));
				}
			}
			else swap(s[p], d[p]);
			FORX(vh)
			{
				if (x == p)continue;
				if (s[x].count(p))s[x].erase(p), d[x].insert(p);
				else if (d[x].count(p))d[x].erase(p), s[x].insert(p);
			}
		}
		else
		{
			I id = 0;
			if (lde.size())
			{
				auto it = lde.begin();
				id = eg[*it];
				I u = it->ft, v = it->sd;
				l[u].erase(v);
				l[v].erase(u);
				lde.erase(it);
			}
			else
			{
				FORX(vh)
				{
					if (d[x].empty())continue;
					I u = x, v = *d[x].begin();
					d[u].erase(v);
					if (ish[v])d[v].erase(u);
					id = eg[make(u, v)];
					break;
				}
			}
			W(id);
		}
	}
}

I main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	if (fopen("test.in", "r"))
	{
		freopen("test.in", "r", stdin);
		freopen("test.out", "w", stdout);
	}
	I t = 1;
	// R(t);
	while (t--)test();
	return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3504kb

input:

output:

result:

ok q=10

Test #2:

score: 0

Accepted

time: 0ms

memory: 3572kb

input:

0 0
0

output:

result:

ok q=0

Test #3:

score: 0

Accepted

time: 0ms

memory: 3476kb

input:

0 0
1
?

output:

result:

ok q=1

Test #4:

score: 0

Accepted

time: 5ms

memory: 4092kb

input:

output:

result:

ok q=100000

Test #5:

score: 0

Accepted

time: 3695ms

memory: 19636kb

input:

output:

result:

ok q=100000

Test #6:

score: 0

Accepted

time: 2858ms

memory: 18520kb

input:

output:

result:

ok q=100000

Test #7:

score: 0

Accepted

time: 2103ms

memory: 18452kb

input:

output:

result:

ok q=100000

Test #8:

score: 0

Accepted

time: 1419ms

memory: 18556kb

input:

output:

result:

ok q=100000

Test #9:

score: 0

Accepted

time: 880ms

memory: 18536kb

input:

output:

result:

ok q=100000

Test #10:

score: 0

Accepted

time: 404ms

memory: 18496kb

input:

output:

result:

ok q=100000

Test #11:

score: 0

Accepted

time: 80ms

memory: 17340kb

input:

output:

result:

ok q=100000

Test #12:

score: 0

Accepted

time: 3667ms

memory: 19436kb

input:

output:

result:

ok q=100000

Test #13:

score: 0

Accepted

time: 2780ms

memory: 18480kb

input:

output:

result:

ok q=100000

Test #14:

score: 0

Accepted

time: 2058ms

memory: 18556kb

input:

output:

result:

ok q=100000

Test #15:

score: 0

Accepted

time: 1442ms

memory: 18532kb

input:

output:

result:

ok q=100000

Test #16:

score: 0

Accepted

time: 870ms

memory: 18392kb

input:

output:

result:

ok q=100000

Test #17:

score: 0

Accepted

time: 422ms

memory: 18388kb

input:

output:

result:

ok q=100000

Test #18:

score: 0

Accepted

time: 78ms

memory: 18576kb

input:

output:

result:

ok q=100000

Test #19:

score: 0

Accepted

time: 3815ms

memory: 19452kb

input:

output:

result:

ok q=100000

Test #20:

score: 0

Accepted

time: 2820ms

memory: 19444kb

input:

output:

result:

ok q=100000

Test #21:

score: 0

Accepted

time: 2029ms

memory: 19528kb

input:

output:

result:

ok q=100000

Test #22:

score: 0

Accepted

time: 1389ms

memory: 19540kb

input:

output:

result:

ok q=100000

Test #23:

score: 0

Accepted

time: 868ms

memory: 19624kb

input:

output:

result:

ok q=100000

Test #24:

score: 0

Accepted

time: 425ms

memory: 19456kb

input:

output:

result:

ok q=100000

Test #25:

score: 0

Accepted

time: 93ms

memory: 19616kb

input:

output:

result:

ok q=100000

Test #26:

score: -100

Time Limit Exceeded

input: