QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#55848	#2827. Autobiography	indogent^#	TL	7ms	12220kb	C++20	1.4kb	2022-10-15 14:00:27	2022-10-15 14:00:28

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-10-15 14:00:28]
评测

测评结果：TL
用时：7ms
内存：12220kb

查看

[2022-10-15 14:00:27]
提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;
typedef long long LL;

#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define repG(u, j) for(int j = hd[u]; j ; j = e[j].nxt)
#define ev e[j].v

struct Edge{int v, nxt;} e[N<<1];
int hd[N], cnt;
void addedge(int u, int v) {e[++ cnt] = (Edge) {v, hd[u]}; hd[u] = cnt;}

int n, m;
char s[N];
LL f[N][5];

int main() {

	while (~scanf("%d%d", &n, &m)) {
		memset(hd, 0, sizeof(hd));
		cnt = 0;
		scanf("%s", s+1);
		rep(i, 1, m) {
			int u, v;
			scanf("%d%d", &u, &v);
			addedge(u, v), addedge(v, u);
		}
		memset(f, 0, sizeof(f));
		rep(i, 1, n) 
			if (s[i] == 'b') 
				f[i][1] = 1;
			else 
				f[i][1] = 0;
		rep(i, 1, 3) 
			rep(u, 1, n) {
				if (s[u] != (i & 1 ? 'b' : 'o') ) continue ;
				//printf("%d %d : %d\n", u, i, f[u][i]);
				repG(u, j) {
					//cout << ev << endl;
					if (s[ev] != ((i&1) ^ 1 ? 'b' : 'o')) continue ;
					f[ev][i+1] += f[u][i];
				}
			}
		LL ans = 0;
		rep(i, 1, n) ans += f[i][4];//, printf("%d %d : %d\n", i, 4, f[i][4]);
		rep(u, 1, n) {
			int cnto = 0, cntb = 0;
			repG(u, j) 
				if (s[ev] == 'o') cnto ++;
				else cntb ++;
			if (s[u] == 'b') ans -= cnto*cnto;
			else ans -= cntb*(cntb-1);
		}
		cout << ans << endl;
	}

	return 0;
}

/*
5 4
bbobo
1 3
2 3
3 4
4 5
4 6
bobo
1 2
1 3
1 4
2 3
2 4
3 4
4 0
bobo
 */

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 7ms

memory: 12220kb

input:

output:

2
4
0

result:

ok 3 lines

Test #2:

score: -100

Time Limit Exceeded

input:

output: