QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#251924 | #7776. 超现实树 | hos_lyric# | 0 | 240ms | 4672kb | C++14 | 5.3kb | 2023-11-15 13:01:55 | 2024-07-04 02:25:31 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
int N, M;
char C[100'010];
vector<int> A, B;
vector<vector<int>> graph;
namespace brute {
vector<int> stack;
vector<Int> ans;
void dfs(int u, int p, int k) {
if (C[u] == '{') {
stack.push_back(0);
} else if (C[u] == '|') {
if (stack.empty()) return;
++stack.back();
} else if (C[u] == '}') {
if (stack.empty()) return;
if (!~k) k = stack.back();
if (k != stack.back()) return;
stack.pop_back();
} else {
assert(false);
}
if (stack.empty()) {
assert(~k);
++ans[k];
}
for (const int v : graph[u]) if (p != v) {
dfs(v, u, k);
}
if (C[u] == '{') {
stack.pop_back();
} else if (C[u] == '|') {
if (stack.empty()) assert(false);
--stack.back();
} else if (C[u] == '}') {
assert(~k);
stack.push_back(k);
} else {
assert(false);
}
}
vector<Int> run() {
cerr<<"[brute::run]"<<endl;
ans.assign(N, 0);
for (int r = 0; r < N; ++r) {
stack.clear();
dfs(r, -1, -1);
}
return ans;
}
} // brute
namespace sub2 {
vector<Int> run() {
cerr<<"[sub2::run]"<<endl;
vector<Int> ans(N, 0);
for (int phase = 0; phase < 2; ++phase) {
vector<int> hei(N + 1, 0);
vector<int> mate(N, -1);
{
vector<int> stack;
for (int u = 0; u < N; ++u) {
if (C[u] == '{') {
hei[u + 1] = hei[u] + 1;
stack.push_back(u);
} else if (C[u] == '|') {
hei[u + 1] = hei[u];
} else if (C[u] == '}') {
hei[u + 1] = hei[u] - 1;
if (stack.size()) {
const int v = stack.back();
stack.pop_back();
mate[v] = u;
mate[u] = v;
}
}
}
}
vector<pair<int, int>> ps;
for (int u = 0; u < N; ++u) if (u < mate[u]) {
ps.emplace_back(u, mate[u]);
}
sort(ps.begin(), ps.end(), [&](const pair<int, int> &p0, const pair<int, int> &p1) -> bool {
return ((hei[p0.first] != hei[p1.first]) ? (hei[p0.first] > hei[p1.first]) : (p0 < p1));
});
const int psLen = ps.size();
cerr<<"ps = "<<ps<<endl;
vector<int> ids(N, -1);
for (int j = 0; j < psLen; ++j) {
ids[ps[j].first] = ids[ps[j].second] = j;
}
vector<int> ks(psLen, -1);
set<int> ss;
ss.insert(N);
for (int j = 0; j < psLen; ++j) {
auto check = [&](int k) -> void {
if (!~ks[j]) ks[j] = k;
if (ks[j] != k) ks[j] = -2;
};
const int u = ps[j].first;
const int v = ps[j].second;
int sz = v - u - 1;
for (auto it = ss.lower_bound(u); *it < v; it = ss.erase(it)) {
const int x = *it;
const int y = mate[x];
sz -= (y - x + 1);
check(ks[ids[x]]);
}
assert(sz >= 0);
check(sz);
ss.insert(u);
}
cerr<<"ks = "<<ks<<endl;
for (int j0 = 0, j1 = 0; j0 < psLen; j0 = j1) {
for (j1 = j0 + 1; j1 < psLen && ps[j1 - 1].second + 1 == ps[j1].first && ks[j1 - 1] == ks[j1]; ++j1) {}
if (ks[j0] >= 0) {
ans[ks[j0]] += (Int)(j1 - j0) * (j1 - j0 + 1) / 2;
}
}
reverse(C, C + N);
}
return ans;
}
} // sub2
int main() {
for (; ~scanf("%d%d", &N, &M); ) {
scanf("%s", C);
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
graph.assign(N, {});
for (int i = 0; i < N - 1; ++i) {
graph[A[i]].push_back(B[i]);
graph[B[i]].push_back(A[i]);
}
bool spe2 = true;
for (int i = 0; i < N - 1; ++i) {
spe2 = spe2 && (abs(A[i] - B[i]) == 1);
}
vector<Int> ans;
if (spe2) {
ans = sub2::run();
} else {
ans = brute::run();
}
for (int k = 0; k <= M; ++k) {
if (k) printf(" ");
printf("%lld", ans[k]);
}
puts("");
#ifdef LOCAL
const auto brt=brute::run();
if(brt!=ans)cerr<<N<<" "<<M<<" "<<C<<" "<<A<<" "<<B<<": "<<brt<<" "<<ans<<endl;
assert(brt==ans);
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 3ms
memory: 4216kb
input:
4578 4576 |}}|}|{}{}|}|||{}}|}|||{|}||}}{}{{}|{{}|}}{}|{}{{}{{|{}}}|{||}||}}}}}|}}{||}|}{|{{}{}|{}{{}}}|{{}|}{}{}}}}}||}|}||||||{|}{}|}{|}{|}||}}}|}{{|}{{{}{}||{}}||}{}|}}{||{}}{}}|{|}{{|}}|{}||}}{}||}}|{|{{|}|{{}|{{{}}|||{}|||{{}}{||}{{|{{{{|{|}{|}{||}}}{{|}{}|{}}}{|}}{{|{|}{||{||||{|}}{{|}}{|||}}|...
output:
1736 642 213 88 42 16 8 1 1 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 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 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 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 0 0 0 ...
result:
ok 4577 tokens
Test #2:
score: 0
Accepted
time: 2ms
memory: 4316kb
input:
4598 4596 ||||||||}|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||{|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||{|||||||||||||||||||||||||||||||||||||||||||||||...
output:
1 15 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 3 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 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 0 0 0 0 0 0...
result:
ok 4597 tokens
Test #3:
score: 0
Accepted
time: 233ms
memory: 4672kb
input:
4562 4560 }{}{{}{{{}}}}{{{{{}{{}{{{}}{{}{{{}}}{}{}}{}{{{{}}}{{}{{}}{{{{{{{{{{}}}{}}}}}{{{{{}}}}}{{}}{{}}{}{{}}{}{{}}}}}{{}}}}{{{}{}{}}{}{{{}}{{{{{{{}}}{}}}}}{}}{}{{}{}}}}{}{{{{}}}}{}{{}{}}}}{}}}{}}{{{}}}{{{{}}}}}}{}}{}}{}}{}{{{{}}}}{}{{{{{{{}}}{{{}}}}}{}{}}{}{}}}}{{{}}{}}}{{}}{}}{}}}}}{}}{{}}{}}}{{{...
output:
5094047 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 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 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 4561 tokens
Test #4:
score: 0
Accepted
time: 6ms
memory: 4120kb
input:
4558 4556 ||{{}{}|{}||}}}{||}{{|{|{|||{|}|}|}}}{{}|}}}|}}|{{|||{{|{}}{||}|{}}||||{||{||}|}{|}{||{{{{}||{}}{{}}|||}{}||{|}|{{{}|{|{{}}|}|}}}}|{{|{|}|}|{|}{{}}{}||{}{}||}}|}}|}{|}|{}|}|{|{{{}}}|{|{{{{}}|}{{||{|{{||||}}{|}|{|||{}}}}{{{|{{{|||{{|{{}|{||||}}}||||}}}|{|}}|}{{|}{{{{}{|||}{{|}}{|}{}{{}}}}{}...
output:
2009 734 273 142 84 39 10 1 2 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 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 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 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 0 0 0 ...
result:
ok 4557 tokens
Test #5:
score: 0
Accepted
time: 5ms
memory: 4204kb
input:
4560 4558 {}{{}}}{{{}}{{}}{{{}{}}}}}{{{}{{{}}{{}{{{}}{{}{{}}{}}|{}{{{{}{{}}{}{}}}}{{}|}}}{{}{}}}{}{{}}{}{}|}{{}{{{{{}}}}{{{}}{{{}}}}}}{}}{{{}}}}}}{}}{{}}}{}{{}{{}{}{}}}}}}}{{}}}}}}}}{}{}}{}{}}{{}{}}}}{}}}}}}{}{{{}}}{{}{|}{}}}{{}}}}{}{}{{{{}}{}{{}{}{}{}{{{}}{}}{}{}}}}{}{}{}}{}{{{{{}{}{{}}{}{}{}{}{}}}...
output:
11100 30 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 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 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 4559 tokens
Test #6:
score: 0
Accepted
time: 195ms
memory: 4112kb
input:
4594 4592 {{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{...
output:
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 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 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 4593 tokens
Test #7:
score: 0
Accepted
time: 3ms
memory: 4484kb
input:
4561 4559 {}{{}{{}|{}{||}|}|{|{}|}}||{}||}}{||}}{{{{||}}}}|{|}}|||||{{|{|}}||{||{||{}}|{|{|{|}}||}{}{{}{|{}{{||}||||{|||}{}}}{}{{{{}}|}|}}}}|{}{|{|||{|||}{{{}}|}{}{{}{}|}}|{}|{|{}}{}{}}}|}|}{{}||{|}|}{}|}}}}|{}|}{{{}}{}|}}|}{{|{|}{{||{|}{|}}}}}{{||{}|{{{}{{|}}|{}}{}}}}}||}|{{{{{}}}||}||}|{{{{}}|}}{{...
output:
1828 565 244 83 27 11 1 2 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 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 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 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 0 0 0 0 0 ...
result:
ok 4560 tokens
Test #8:
score: 0
Accepted
time: 35ms
memory: 4248kb
input:
4579 4577 {}}}}}{{}}{{{}}{}{{{}}}}{{{{}{{{{{{{{{{{{{{{}{}{}{}{}{{}}}}{{{}}{}{}{}}}}{{}}{}{}}{{{{}{{{{{{}}{}{}{{{{}}}}}{}{}}}}{{{{{}}{}}}}}{{}}{}}{{}{}{}}{{{}{}{}}{{}{{{}}}{}}{{}{{{}}}}}}{}{}}{{{{}}{{{}}}{{{}}}{{{{}}}}{{}}{{}{{}}}{}{{{{}}}}}}{{{}{{{{}{{{}}{{}}}{{{}}{{}}{{{{}}{{}{}}{}{{}{}}{}{}}}{}}}}...
output:
26457 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 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 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 4578 tokens
Test #9:
score: -5
Wrong Answer
time: 240ms
memory: 4192kb
input:
4557 4555 {}}{{{}}}{}}{}}{}}}{{}}{{{}{}{}{}}}}{}{}}}{{}}{{{}}{}}}{{}{}}}{}{}}}}{{}{}{{}{{{{{}{{{{{}}{}}}}}{{{}{{}}{{{{{{{}{}}{{{}{}{{}}{{}{{{{{}{}{}}{{}}}}}{}{{{{}{}}{{}{}}}{{}{{{{{{}}{{}{}{{}{{{{}{}}}}{{{}{}}}{{{{{}}{}}{}{}{}{}}{}{{}{{}{{}{{}}}}}}}}{}}}}}}{{}{{}{}}}}}}{{{}{}{{}{}}{{}}{}}{{{}{{{}}}{...
output:
result:
wrong output format Output file not found: ""
Subtask #2:
score: 0
Judgement Failed
Test #16:
score: 0
Judgement Failed
input:
99981 99979 }|}{|}|}||{{{{|}}}{|}|}|}||||}}}|||||}|{{|||{|{}||}}{}}}}||{}{{}{{|{}{|}}}{|}||{|{}}|{{{|}{}{}}|}{}}{}||||}{|{{}{|{}}{}}|}}{|}{{}{{}|{|||{|{{}}{}{|}{||}}||}|}|}|{}{{}|}||}{{|{}{}}}||}}|}}||{||||||}}{}}}|}}|}}}}|}}}}||||{}}{{|{{}|}|{{}{|}||}{|}|}||{}}|}|{{{{{||{}}{}|{|}{{{|}|{|{|}}|{|}{}}...
output:
result:
Subtask #3:
score: 0
Judgement Failed
Test #26:
score: 0
Judgement Failed
input:
99990 0 }}}}{{{}{{{{}}}}}{{{{{}}{{}{}}}{}}}{}}}{{{}{{{{}{}}}{{}{{{}{}{}{{{}}{{}}{{{}}{{{{{}{}{}{}}{{{}{}{}{}}{}{}{{}}}{{{}{}{}}{}{}{}}}}}{}{{{}{{{}}{}}}}}{{}}{{{}}}{{}{{}{}{}}{}{}{{}}}}{}{{{}{}{{}{{}{{}}}{}}{{}{}}}}}}}}}}}}{{}}{}{}}}{{{{{}{{{}}{}}{}{{{{}}}{}}}{{}{}{{}{}}{}}}}{}{}{}}{{}}}{}{{}}{{{}}{...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%