QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#835029#8012. Jumping LightsRadewoosh#WA 47ms196492kbC++235.4kb2024-12-28 09:05:372024-12-28 09:05:37

Judging History

This is the latest submission verdict.

  • [2024-12-28 09:05:37]
  • Judged
  • Verdict: WA
  • Time: 47ms
  • Memory: 196492kb
Show
  • [2024-12-28 09:05:37]
  • Submitted

answer

//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=1000*1007;

int n, q;

int ojc[nax];
vi graf[nax];

int parz[nax];

int ile[2][2];
int stan;

int czyl[nax];

set<pii> zazdz[2][nax];
set<pii> niedz[2][nax];

int zazn[2][nax];

vi swieze[2];

void dfs1(int v)
{
	for (int &i : graf[v])
	{
		if (i==ojc[v])
		{
			swap(i, graf[v].back());
			graf[v].pop_back();
			break;
		}
	}
	for (int i : graf[v])
	{
		ojc[i]=v;
		parz[i]=parz[v]^1;
		dfs1(i);
	}
}

int wynik()
{
	return ile[0][stan]+ile[1][stan^1];
}

void flip(int kt, int v)
{
	//~ debug() << "flipuje " << imie(kt) << imie(v);
	if (zazn[kt][v])
	{
		ile[kt][parz[v]]--;
		zazn[kt][v]=0;
		if (v>1)
		{
			//~ iledz[kt][ojc[v]]--;
			zazdz[kt][ojc[v]].erase({!czyl[v], v});
			niedz[kt][ojc[v]].insert({!czyl[v], v});
		}
	}
	else
	{
		ile[kt][parz[v]]++;
		zazn[kt][v]=1;
		if (v>1)
		{
			//~ iledz[kt][ojc[v]]++;
			zazdz[kt][ojc[v]].insert({!czyl[v], v});
			niedz[kt][ojc[v]].erase({!czyl[v], v});
		}
	}
}

int isfake(int kt, int v)
{
	return zazn[kt][v] && parz[v]!=(stan^kt) && !(zazn[kt][ojc[v]]+(int)zazdz[kt][v].size());
}

void rozszerz(int kt)//najpierw usun spojne rozmiaru jeden zlej parzystosci
{
	vi dod;
	vi pom=swieze[kt];
	swieze[kt].clear();
	
	sort(pom.begin(), pom.end());
	pom.resize(unique(pom.begin(), pom.end())-pom.begin());
	
	for (int i : pom)
	{
		if (parz[i]!=(stan^kt))
		{
			if (isfake(kt, i))
				flip(kt, i);
			//~ else
				//~ swieze[kt].push_back(i);
		}
		else
		{
			if (!zazn[kt][i])
			{
				if (i>1 && isfake(kt, ojc[i]))
					flip(kt, ojc[i]);
				if (i>1 && !isfake(kt, ojc[i]) && zazn[kt][ojc[i]])
					swieze[kt].push_back(ojc[i]);
				while(1)
				{
					if (zazdz[kt][i].empty())
						break;
					int d=(*zazdz[kt][i].begin()).second;
					if (!isfake(kt, d))
					{
						swieze[kt].push_back(d);
						break;
					}
					flip(kt, d);
				}
				
				//~ swieze[kt].push_back(i);
			}
		}
	}
	
	//~ debug() << imie(kt) << imie(pom);
	
	for (int i : pom)
	{
		//~ debug() << imie(i) << imie(zazn[kt][i]) << imie(parz[i]==(stan^kt));
		if (!zazn[kt][i] && parz[i]!=(kt^stan))//zaraza sie
		{
			int jest=0;
			if (i>1 && zazn[kt][ojc[i]])
			{
				if (isfake(kt, ojc[i]))
					flip(kt, ojc[i]);
				else
					jest=1;
			}
			while(!jest && !zazdz[kt][i].empty())
			{
				int d=(*zazdz[kt][i].begin()).second;
				if (isfake(kt, d))
					flip(kt, d);
				else
					jest=1;
			}
			
			if (!jest)
				continue;
			
			dod.push_back(i);
			continue;
		}
		if (zazn[kt][i] && parz[i]==(kt^stan))//zaraza somsiadow
		{
			if (i>1 && !zazn[kt][ojc[i]])
				dod.push_back(ojc[i]);
			for (pii j : niedz[kt][i])
				dod.push_back(j.second);
			continue;
		}
		//~ if (zazn[kt][i])
			//~ swieze[kt].push_back(i);
	}
	
	sort(dod.begin(), dod.end());
	dod.resize(unique(dod.begin(), dod.end())-dod.begin());
	
	for (int i : dod)
	{
		if (!zazn[kt][i])
		//~ {
			flip(kt, i);
			swieze[kt].push_back(i);
		//~ }
	}
	
}

int main()
{
	scanf("%d%d", &n, &q);
	for (int i=1; i<n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		graf[a].push_back(b);
		graf[b].push_back(a);
	}
	for (int i=1; i<=n; i++)
		czyl[i]=(((int)graf[i].size())==1);
	dfs1(1);
	for (int h=0; h<2; h++)
		for (int i=2; i<=n; i++)
			niedz[h][ojc[i]].insert({!czyl[i], i});
	while(q--)
	{
		int typ;
		scanf("%d", &typ);
		if (typ<=1)
		{
			int v;
			scanf("%d", &v);
			
			for (int i=0; i<2; i++)
			{
				if (parz[v]!=(stan^i))
					continue;
				if (zazn[i][v]!=typ)
					flip(i, v);
				swieze[i].push_back(v);
			}
		}
		if (typ==2)
		{
			rozszerz(0);
			rozszerz(1);
			stan^=1;
		}
		printf("%d ", wynik());
		debug();
		debug() << range(zazn[0]+1, zazn[0]+1+n);
		debug() << range(zazn[1]+1, zazn[1]+1+n);
		debug() << imie(swieze[0]) << imie(swieze[1]);
		debug();
	}
	printf("\n");
	return 0;
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 36ms
memory: 194228kb

input:

8 8
1 2
2 3
2 4
1 5
5 6
5 7
5 8
1 1
2
2
0 1
0 3
0 4
0 5
2

output:

1 2 6 5 4 3 3 1

result:

ok 8 numbers

Test #2:

score: 0
Accepted
time: 40ms
memory: 194252kb

input:

4 5
1 2
1 3
2 4
1 2
2
0 4
2
2

output:

1 2 1 2 2

result:

ok 5 number(s): "1 2 1 2 2"

Test #3:

score: 0
Accepted
time: 47ms
memory: 194360kb

input:

1000 1000
471 906
653 752
346 148
764 837
22 863
416 906
836 863
784 752
694 346
918 635
963 863
152 863
221 342
473 752
250 635
323 643
102 643
944 833
262 752
185 150
82 342
142 342
383 635
1000 342
30 752
713 837
513 635
12 150
181 346
138 752
661 150
435 342
246 150
387 643
561 635
41 833
797 34...

output:

1 1 2 115 114 118 117 103 102 306 305 396 395 604 603 497 496 810 809 692 691 908 907 695 694 907 906 599 598 906 905 493 492 905 904 492 491 904 903 395 394 903 902 394 393 805 804 393 392 710 709 392 391 709 708 390 389 611 610 389 388 498 497 387 386 402 401 386 385 401 400 298 297 400 399 297 29...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 35ms
memory: 194476kb

input:

1000 1000
471 906
653 752
346 148
764 837
22 863
416 906
836 863
784 752
694 346
918 635
963 863
152 863
221 342
473 752
250 635
323 643
102 643
944 833
262 752
185 150
82 342
142 342
383 635
1000 342
30 752
713 837
513 635
12 150
181 346
138 752
661 150
435 342
246 150
387 643
561 635
41 833
797 34...

output:

1 2 3 4 4 5 5 501 14 14 15 15 804 804 804 804 803 802 296 296 296 296 296 296 296 907 906 905 904 904 904 904 903 902 903 694 693 693 1000 1000 1000 1000 999 1000 1000 1000 1000 1000 1000 999 998 998 998 1000 1000 1000 1000 1000 1000 999 999 999 999 998 998 997 997 996 1000 1000 1000 1000 1000 1000 ...

result:

ok 1000 numbers

Test #5:

score: -100
Wrong Answer
time: 41ms
memory: 196492kb

input:

1000 1000
381 447
194 664
14 628
379 159
314 696
462 431
288 881
94 715
841 505
356 729
973 447
605 433
370 664
733 785
591 779
961 35
770 294
723 580
924 431
472 606
315 858
612 526
538 638
562 890
241 686
717 611
673 937
25 81
342 269
132 159
97 418
647 58
552 930
962 858
996 219
155 219
446 18
96...

output:

1 1 2 3 2 26 25 71 70 86 85 139 138 143 142 187 186 203 202 265 264 269 268 291 290 334 333 357 356 401 400 426 425 469 468 491 490 535 534 560 559 609 608 625 624 675 674 691 690 736 735 748 747 791 790 817 816 857 856 874 873 924 923 949 948 965 964 954 953 964 963 953 952 946 945 951 950 945 944 ...

result:

wrong answer 450th numbers differ - expected: '690', found: '689'
English 繁體中文 简体中文

伺服器時間: 2025-02-08 23:58:21 | 開源專案