QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#342030#905. 三元环枚举Ishy#AC ✓217ms10424kbC++142.4kb2024-03-01 08:03:122024-03-01 08:03:14

Judging History

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

  • [2024-03-01 08:03:14]
  • 评测
  • 测评结果:AC
  • 用时:217ms
  • 内存:10424kb
  • [2024-03-01 08:03:12]
  • 提交

answer

// Sea, You & Me
#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 998244353
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) ((-x) & x)
#define MP make_pair
#define MT make_tuple
#define VI vector<int>
#define VL vector<LL>
#define VII VI::iterator
#define VLI VL::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define PII pair<int, int>
#define PLI pair<LL, int>
#define SI set<int>
#define SII SI::iterator
#define fi first
#define se second
using namespace std;
template<typename T> void chkmn(T &a, const T b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T b) { (a < b) && (a = b); }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int inc(const int &a, const int &b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return (a - b < 0) ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
	int res = 1;
	while(k)
	{
		if(k & 1) Mul(res, x);
		k >>= 1, Sqr(x);
	}
	return res;
}
template<typename T> void read(T &x)
{
	x = 0;
	int f = 1;
	char ch = getchar();
	while(!isdigit(ch))
	{
		if(ch == '-')
			f = -1;
		ch = getchar();
	}
	while(isdigit(ch))
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x = x * f;
}
const int N = 1e5 + 5;
const int M = 2e5 + 5;
int n, m, a[N];
vector<int> G[N];
int d[N], vis[N];
bool cmp(int x, int y)
{
	if(d[x] != d[y])
		return d[x] > d[y];
	return x > y;
}
int main()
{
	read(n), read(m);
	for(int i = 1; i <= n; ++i)
		read(a[i]);
	for(int i = 1; i <= m; ++i)
	{
		int u, v;
		read(u), read(v);
		++u, ++v;
		++d[u], ++d[v];
		G[u].EB(v), G[v].EB(u);
	}
	int ans = 0;
	for(int u = 1; u <= n; ++u)
	{
		for(auto v : G[u])
		{
			if(!cmp(u, v)) continue;
			vis[v] = u;
		}
		for(auto v : G[u])
		{
			if(!cmp(u, v)) continue;
			for(auto w : G[v])
			{
				if(!cmp(u, w)) continue;
				if(!cmp(v, w)) continue;
				if(vis[w] != u) continue;
				Inc(ans, mul(a[u], mul(a[v], a[w])));
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 6200kb

input:

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

output:

36

result:

ok "36"

Test #2:

score: 0
Accepted
time: 14ms
memory: 8280kb

input:

17707 77101
528756313 434883274 318065816 264440383 659789617 608119380 648104885 725454492 696703871 543030428 663661240 890791532 108201616 428505484 322953840 119811886 691103780 306647414 549862302 176916719 909058872 455464665 307270851 584469329 722629343 875317523 629938577 244419357 78121457...

output:

397965084

result:

ok "397965084"

Test #3:

score: 0
Accepted
time: 8ms
memory: 7920kb

input:

69830 19691
136987924 40280999 438515315 805152546 234164454 129099933 971852321 983937488 410134225 668461222 574343409 885417013 394300887 86086437 570981511 221329455 57893312 584381871 154204049 738660729 728257729 551666498 540440394 165573287 512342480 452470821 669622703 340240729 965382636 9...

output:

0

result:

ok "0"

Test #4:

score: 0
Accepted
time: 16ms
memory: 8828kb

input:

53336 61958
288974909 111681588 291303632 155763712 177741457 164199418 280452914 745629015 727272894 383855815 451963117 263419161 854025925 625817844 903511050 636159790 788165373 442332844 275132246 358996390 239303569 23523747 398318281 935986353 142493592 695297770 499848367 7061287 551242323 6...

output:

906430555

result:

ok "906430555"

Test #5:

score: 0
Accepted
time: 217ms
memory: 7424kb

input:

447 99681
192279220 156648746 154396384 640494892 528756313 434883274 318065816 264440383 659789617 608119380 648104885 725454492 696703871 543030428 663661240 890791532 108201616 428505484 322953840 119811886 691103780 306647414 549862302 176916719 909058872 455464665 307270851 584469329 722629343 ...

output:

687388905

result:

ok "687388905"

Test #6:

score: 0
Accepted
time: 23ms
memory: 10084kb

input:

100000 100000
192279220 156648746 154396384 640494892 528756313 434883274 318065816 264440383 659789617 608119380 648104885 725454492 696703871 543030428 663661240 890791532 108201616 428505484 322953840 119811886 691103780 306647414 549862302 176916719 909058872 455464665 307270851 584469329 722629...

output:

544299331

result:

ok "544299331"

Test #7:

score: 0
Accepted
time: 20ms
memory: 10028kb

input:

100000 100000
264704197 120999146 136987924 40280999 438515315 805152546 234164454 129099933 971852321 983937488 410134225 668461222 574343409 885417013 394300887 86086437 570981511 221329455 57893312 584381871 154204049 738660729 728257729 551666498 540440394 165573287 512342480 452470821 669622703...

output:

173075458

result:

ok "173075458"

Test #8:

score: 0
Accepted
time: 19ms
memory: 10124kb

input:

100000 100000
682152023 451794314 2028037 288974909 111681588 291303632 155763712 177741457 164199418 280452914 745629015 727272894 383855815 451963117 263419161 854025925 625817844 903511050 636159790 788165373 442332844 275132246 358996390 239303569 23523747 398318281 935986353 142493592 695297770...

output:

914677810

result:

ok "914677810"

Test #9:

score: 0
Accepted
time: 1ms
memory: 6172kb

input:

2 1
1 2
0 1

output:

0

result:

ok "0"

Test #10:

score: 0
Accepted
time: 2ms
memory: 6204kb

input:

181 1323
154396384 640494892 528756313 434883274 318065816 264440383 659789617 608119380 648104885 725454492 696703871 543030428 663661240 890791532 108201616 428505484 322953840 119811886 691103780 306647414 549862302 176916719 909058872 455464665 307270851 584469329 722629343 875317523 629938577 2...

output:

810000936

result:

ok "810000936"

Test #11:

score: 0
Accepted
time: 23ms
memory: 6400kb

input:

198 17685
40280999 438515315 805152546 234164454 129099933 971852321 983937488 410134225 668461222 574343409 885417013 394300887 86086437 570981511 221329455 57893312 584381871 154204049 738660729 728257729 551666498 540440394 165573287 512342480 452470821 669622703 340240729 965382636 953292241 144...

output:

893263934

result:

ok "893263934"

Test #12:

score: 0
Accepted
time: 2ms
memory: 6172kb

input:

88 1419
2028037 288974909 111681588 291303632 155763712 177741457 164199418 280452914 745629015 727272894 383855815 451963117 263419161 854025925 625817844 903511050 636159790 788165373 442332844 275132246 358996390 239303569 23523747 398318281 935986353 142493592 695297770 499848367 7061287 5512423...

output:

285141028

result:

ok "285141028"

Test #13:

score: 0
Accepted
time: 0ms
memory: 6176kb

input:

181 299
154396384 640494892 528756313 434883274 318065816 264440383 659789617 608119380 648104885 725454492 696703871 543030428 663661240 890791532 108201616 428505484 322953840 119811886 691103780 306647414 549862302 176916719 909058872 455464665 307270851 584469329 722629343 875317523 629938577 24...

output:

68968143

result:

ok "68968143"

Test #14:

score: 0
Accepted
time: 1ms
memory: 6152kb

input:

198 235
136987924 40280999 438515315 805152546 234164454 129099933 971852321 983937488 410134225 668461222 574343409 885417013 394300887 86086437 570981511 221329455 57893312 584381871 154204049 738660729 728257729 551666498 540440394 165573287 512342480 452470821 669622703 340240729 965382636 95329...

output:

273857930

result:

ok "273857930"

Test #15:

score: 0
Accepted
time: 0ms
memory: 6284kb

input:

88 139
2028037 288974909 111681588 291303632 155763712 177741457 164199418 280452914 745629015 727272894 383855815 451963117 263419161 854025925 625817844 903511050 636159790 788165373 442332844 275132246 358996390 239303569 23523747 398318281 935986353 142493592 695297770 499848367 7061287 55124232...

output:

351774600

result:

ok "351774600"

Test #16:

score: 0
Accepted
time: 16ms
memory: 10420kb

input:

100000 99999
192279220 156648746 154396384 640494892 528756313 434883274 318065816 264440383 659789617 608119380 648104885 725454492 696703871 543030428 663661240 890791532 108201616 428505484 322953840 119811886 691103780 306647414 549862302 176916719 909058872 455464665 307270851 584469329 7226293...

output:

0

result:

ok "0"

Test #17:

score: 0
Accepted
time: 14ms
memory: 10424kb

input:

100000 99999
264704197 120999146 136987924 40280999 438515315 805152546 234164454 129099933 971852321 983937488 410134225 668461222 574343409 885417013 394300887 86086437 570981511 221329455 57893312 584381871 154204049 738660729 728257729 551666498 540440394 165573287 512342480 452470821 669622703 ...

output:

0

result:

ok "0"