QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55848#2827. Autobiographyindogent#TL 7ms12220kbC++201.4kb2022-10-15 14:00:272022-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
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 12220kb

input:

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

output:

2
4
0

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

4 4
oobo
2 3
4 1
4 3
3 1
4 3
obob
1 4
2 3
1 2
4 4
obob
3 1
2 3
2 1
1 4
4 3
bboo
2 4
4 1
3 4
4 3
bbbo
1 4
1 3
4 2
4 4
obbo
3 4
2 4
2 3
3 1
4 3
bobo
2 3
4 3
1 4
4 3
obbb
3 4
4 2
1 4
4 5
bobo
4 1
2 1
3 1
4 3
2 4
4 4
obbo
3 4
3 1
2 3
1 4
4 3
bobb
4 2
4 1
2 3
4 3
obbo
3 1
3 2
1 2
4 4
ooob
2 1
3 1
3 4
1 4...

output:

0
1
1
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
4
1
0
0
0
0
4
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
...

result: