QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#588756#6837. AC Automatoncyj888WA 2ms21520kbC++116.5kb2024-09-25 14:21:272024-09-25 14:21:27

Judging History

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

  • [2024-09-25 14:21:27]
  • 评测
  • 测评结果：WA
  • 用时：2ms
  • 内存：21520kb
查看
  • [2024-09-25 14:21:27]
  • 提交

answer

#include <bits/stdc++.h>
#define ott(i,l,r) for (register int i = l; i <= r; ++ i)
#define read(x) {x = 0; char c; while ((c = getchar ()) < 48); do x = (x << 3) + (x << 1) + (c ^ 48); while ((c = getchar ()) > 47);}
#define print() {long long x = res; len = 0; if (!x) putchar (48); while (x) pc[++ len] = x % 10, x /= 10; while (len) putchar (pc[len --] + 48); putchar ('\n');}
#define cdn1(ttu) {int tu, u = ttu; while (u) {if (u <= LIM) {tu = val[u]; if (!(ch[tu] ^ '?')) res -= Max (dn[tu] - up[tu]); ++ dn[tu]; if (ch[tu] == 'A') ++ res; if (!(ch[tu] ^ '?')) res += Max (dn[tu] - up[tu]);} else b[u - LIM].add (-1), res += b[u - LIM].ac; u = FA[u];}}
#define cdn2(ttu) {int tu, u = ttu; while (u) {if (u <= LIM) {tu = val[u]; if (!(ch[tu] ^ '?')) res -= Max (dn[tu] - up[tu]); -- dn[tu]; if (ch[tu] == 'A') -- res; if (!(ch[tu] ^ '?')) res += Max (dn[tu] - up[tu]);} else b[u - LIM].add (1), res -= b[u - LIM].ac; u = FA[u];}}
using namespace std;
const int N = 3e5 + 110, B = 800, inf = 0x3f3f3f3f;
int n, m, q, idx, len, Z, OTH, LIM;
long long res;
char pc[65];
vector <int> e[N], E[B << 2];
int up[N], dn[N], dfn[N], dep[N], fa[N], lg[N << 1], f[N << 1][20];
char ch[N];
void dfs0 (int u) {
	f[dfn[u] = ++ idx][0] = u, dep[u] = dep[fa[u]] + 1;
	for (int v : e[u]) {
		dfs0 (v);
		f[++ idx][0] = u;
	}
	return ;
}
inline int lca (int x, int y) {
	x = dfn[x], y = dfn[y];
	if (x > y) swap (x, y);
	Z = lg[y - x + 1], x = f[x][Z], y = f[y - (1 << Z) + 1][Z];
	return dep[x] < dep[y] ? x : y;
}
struct OPT {
	int x; char c;
} a[B + 1];
struct BLOCK {
	int ac, now, val, sum;//ac = 'A'count
	vector <int> s; vector <pair <int, int> > t;
	inline void upd (int i) {
		if (!(ch[i] ^ 'A')) ++ ac;
		if (!(ch[i] ^ '?')) {
			i = dn[i] - up[i];
			if (i >= 0) ++ sum;
			if (-m <= i && i <= m) s.emplace_back (i);
		}
		return ;
	}
	inline void init () {
		t.emplace_back (-inf, 0);
		if (s.size ()) {
			sort (s.begin (), s.end ());
			ott (i, 0, s.size () - 1) {
	        	int cnt = 1; while (i + 1 < s.size () && !(s[i] ^ s[i + 1])) ++ i, ++ cnt;
	        	t.emplace_back (s[i], cnt);
			}
		}
		t.emplace_back (inf, 0);
		int l = 0, r = t.size () - 1, mid;
		while (l <= r) {
			mid = l + r >> 1;
			if (t[mid].first >= 0) now = mid, r = mid - 1;
			else l = mid + 1;
		}
		return ;
	}
	inline void add (int v) {
		if (!(v ^ 1)) {
			if (!(t[now].first ^ val ++)) sum -= t[now ++].second;
			res -= sum;
		}
		if (!(v ^ -1)) {
			res += sum;
			if (!(t[now - 1].first ^ -- val)) sum += t[-- now].second;
		}
		return ;
	}
	inline void clear () {
		ac = now = val = sum = 0, vector <int> ().swap (s), vector <pair <int, int> > ().swap (t);
		return ;
	}
} b[B << 1 | 1];
int id[N], val[B << 2], FA[B << 2];
inline int Max (const int &x) {
	return x > 0 ? x : 0;
}
inline bool cmp (const int &x, const int &y) {
	return dfn[x] < dfn[y];
}
void push (int u, int z) {
	b[z].upd (u); for (int v : e[u]) push (v, z); 
	return ;
}

bitset <B << 1> fkd;
void find (int x) {
	if (id[fa[x]]) {
		val[Z = id[x] = ++ idx] = x, Z -= LIM;
		if (fkd[id[fa[x]]]) return ;
	}
	else find (fa[x]), b[Z].upd (fa[x]);
	for (int v : e[fa[x]]) {
		if (!(v ^ x)) continue;
		if (!OTH) val[OTH = id[v] = ++ idx] = v, OTH -= LIM;
		push (v, OTH);
	}
	return ;
}
//void find (int x) {
//	if (id[fa[x]]) {
//		val[Z = id[x] = ++ idx] = x, Z -= LIM;
//		return ;
//	}
//	find (fa[x]), b[Z].upd (fa[x]);
//	for (int v : e[fa[x]]) {
//		if (!(v ^ x)) continue;
//		if (!OTH) val[OTH = id[v] = ++ idx] = v, OTH -= LIM;
//		push (v, OTH);
//	}
//	return ;
//} 
void red (int u) {
	dn[u] = 0;
	for (int v : e[u]) {
		up[v] = up[u]; if (ch[u] ^ 'C') ++ up[v];
		red (v);
		dn[u] += dn[v]; if (ch[v] ^ 'A') ++ dn[u];
	}
	if (!(ch[u] ^ 'A')) res += dn[u];
	if (!(ch[u] ^ '?')) res += Max (dn[u] - up[u]);
	return ;
}
void cup (int u, int V) {
	for (int v : E[u]) {
		if (v <= LIM) {
			int tv = val[v];
			if (!(ch[tv] ^ '?')) res -= Max (dn[tv] - up[tv]);
			up[tv] += V;
			if (!(ch[tv] ^ '?')) res += Max (dn[tv] - up[tv]);
		}
		else b[v - LIM].add (V);
		cup (v, V);
	}
	return ;
}
void sol () {
    ott (i, 1, m) val[i] = a[i].x; 
	idx = m, sort (val + 1, val + 1 + idx), idx = unique (val + 1, val + 1 + idx) - val - 1, sort (val + 1, val + 1 + idx, cmp);
    ott (i, 2, idx) val[idx + i - 1] = lca (val[i - 1], val[i]); 
	val[idx += idx] = 1, sort (val + 1, val + 1 + idx), idx = unique (val + 1, val + 1 + idx) - val - 1;
    ott (i, 1, idx) id[val[i]] = i; LIM = idx;
	ott (i, 2, LIM) {
    	if (!id[fa[val[i]]]) {
    		OTH = Z = 0, find (val[i]);
    		if (OTH) OTH += LIM, E[FA[OTH] = i].emplace_back (OTH);
    		Z += LIM, E[FA[Z] = id[fa[val[Z]]]].emplace_back (Z), E[FA[i] = Z].emplace_back (i), fkd[id[fa[val[Z]]]] = 1;
		}
		else E[FA[i] = id[fa[val[i]]]].emplace_back (i);
	}
	ott (i, 1, LIM) {
		if (fkd[i]) {fkd[i] = 0; continue;}
		OTH = 0; for (int v : e[val[i]]) {
		    if (id[v]) continue;
			if (!OTH) val[OTH = id[v] = ++ idx] = v, OTH -= LIM;
			push (v, OTH);
		}
		if (OTH) OTH += LIM, E[FA[OTH] = i].emplace_back (OTH);
	}
//	ott (i, 1, LIM) {
//		OTH = 0; for (int v : e[val[i]]) {
//			if (id[v]) continue;
//			if (!OTH) {
//				val[OTH = id[v] = ++ idx] = v;
//				E[FA[OTH] = i].emplace_back (OTH), OTH -= LIM;
//			}
//			push (v, OTH);
//		}
//	}
	Z = idx - LIM; ott (i, 1, Z) b[i].init ();
	ott (i, 1, m) {
		int x = a[i].x; char c = a[i].c;
		if (ch[x] ^ 'C') cup (id[x], -1); if (ch[x] ^ 'A') cdn2 (FA[id[x]]);
		if (!(ch[x] ^ 'A')) res -= dn[x];
		if (!(ch[x] ^ '?')) res -= Max (dn[x] - up[x]);
		ch[x] = c;
		if (!(ch[x] ^ 'A')) res += dn[x];
		if (!(ch[x] ^ '?')) res += Max (dn[x] - up[x]);
		if (ch[x] ^ 'C') cup (id[x], 1); if (ch[x] ^ 'A') cdn1 (FA[id[x]]);
		print ();
	}
	ott (i, 1, idx) E[i].clear (), FA[i] = 0, id[val[i]] = 0, val[i] = 0;
	Z = idx - LIM, m = idx = 0, res = 0, red (1); ott (i, 1, Z) b[i].clear ();
	return ;
}
int main () {
	//freopen ("data.in", "r", stdin); freopen ("res.out", "w", stdout);
	read (n); read (q); ott (i, 1, n) ch[i] = getchar (); ott (i, 2, n) {
		read (fa[i]); e[fa[i]].emplace_back (i);
	}
	dfs0 (1), red (1);
	ott (j, 1, 19) {
		ott (i, 1, idx - (1 << j) + 1) {
			OTH = f[i][j - 1], LIM = f[i + (1 << j - 1)][j - 1];
			f[i][j] = dep[OTH] < dep[LIM] ? OTH : LIM;
		}
	}
	lg[0] = -1;	ott (i, 1, idx) lg[i] = lg[i >> 1] + 1; idx = 0;
	int x; char c;
	ott (i, 1, q) {
		read (x); c = getchar ();
		if (!(i % B) || !(i ^ q)) a[m = i % B ? i % B : B] = {x, c}, sol ();
		else a[i % B] = {x, c};
	}
	return 0;
}
源文件, 语言: C++11

詳細信息

Test #1:

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

input:

5 3
AC??C
1 2 2 1
1 ?
4 A
2 ?

output:

4
3
3

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 21496kb

input:

1000 1000
AC?ACCCCC?CCA??CCCCC?A?AC?C??C?ACCCACC?C?CCC?CACACA???????C?????CC?C?AAAAACCA??AAAACACACA???AACAC?CCC?CAC?AAAACCAC???ACAA??A??A?CA?A?ACACACCAA?ACACA?AC??AC??ACAAACCC??CAA?A???CC?AA??AC???A?CCCC??CACCAACC?AA?C?AAACCCA?AAA??C?CC??CACCACAACCA?AACCC?A?CCC?CC???AA?CACCCAAC??CAA??C?AA??CA???CAAA...

output:

2344
2345
2341
2341
2660
2660
2665
2665
2665
2671
2671
2671
2671
2662
2662
2662
2662
2659
2661
2661
2664
2660
2656
2659
2662
2667
2667
2603
2603
2603
2603
2610
2610
2610
2610
2607
2604
2607
2615
2585
2585
2579
2570
2574
2574
2574
2574
2574
2576
2576
2606
2609
2609
2607
2610
2612
2615
2609
2613
2615
...

result:

wrong answer 3rd lines differ - expected: '2342', found: '2341'
English 繁體中文 简体中文

伺服器時間: 2024-11-30 20:51:25 | 開源專案