QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372059 | #2428. Comma Sprinkler | cciafrino# | AC ✓ | 149ms | 18776kb | C++20 | 1.9kb | 2024-03-30 20:40:11 | 2024-03-30 20:40:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
string S;
vector<string> distinct_words;
map<string, int> words_seen;
vector<int> words_id;
vector<char> v;
int cnt = 0;
while (cin >> S) {
const int N = int(S.size());
char last = S.back();
if (last == '\n') break;
else if (last == '.' || last == ',') {
S = S.substr(0, S.size()-1);
v.push_back(last);
} else {
v.push_back('~');
}
if (words_seen.count(S)) {
words_id.push_back(words_seen[S]);
} else {
words_id.push_back(cnt);
words_seen[S] = cnt++;
distinct_words.push_back(S);
}
}
int M = int(v.size());
vector<bool> has_comma(2*cnt);
vector<int> par(2*cnt, -1);
auto find = [&](int a) -> int {
while (par[a] >= 0) {
if (par[par[a]] >= 0) par[a] = par[par[a]];
a = par[a];
}
return a;
};
auto merge = [&](int a, int b) -> bool {
a = find(a), b = find(b);
if (a == b) return false;
if (par[a] > par[b]) swap(a, b);
par[a] += par[b];
par[b] = a;
return true;
};
for (int i = 0; i+1 < M; ++i) {
if (v[i] != '.') {
merge(words_id[i]*2 + 1, words_id[i+1]*2);
}
}
for (int i = 0; i+1 < M; ++i) {
if (v[i] == ',') {
has_comma[find(words_id[i]*2 + 1)] = true;
}
}
for (int i = 0; i < M; ++i) {
cout << distinct_words[words_id[i]];
if (v[i] == '.') cout << '.';
else if (has_comma[find(words_id[i]*2 + 1)]) {
cout << ',';
}
cout << ' ';
}
cout << '\n';
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3584kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3544kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 3636kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3592kb
Test #6:
score: 0
Accepted
time: 33ms
memory: 6216kb
Test #7:
score: 0
Accepted
time: 61ms
memory: 15816kb
Test #8:
score: 0
Accepted
time: 68ms
memory: 15916kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 3580kb
Test #10:
score: 0
Accepted
time: 0ms
memory: 3532kb
Test #11:
score: 0
Accepted
time: 1ms
memory: 3548kb
Test #12:
score: 0
Accepted
time: 1ms
memory: 3764kb
Test #13:
score: 0
Accepted
time: 1ms
memory: 3588kb
Test #14:
score: 0
Accepted
time: 1ms
memory: 3608kb
Test #15:
score: 0
Accepted
time: 0ms
memory: 3552kb
Test #16:
score: 0
Accepted
time: 75ms
memory: 6128kb
Test #17:
score: 0
Accepted
time: 93ms
memory: 7664kb
Test #18:
score: 0
Accepted
time: 139ms
memory: 14580kb
Test #19:
score: 0
Accepted
time: 1ms
memory: 3592kb
Test #20:
score: 0
Accepted
time: 149ms
memory: 17772kb
Test #21:
score: 0
Accepted
time: 110ms
memory: 18776kb
Test #22:
score: 0
Accepted
time: 110ms
memory: 17584kb
Test #23:
score: 0
Accepted
time: 18ms
memory: 7700kb
Test #24:
score: 0
Accepted
time: 132ms
memory: 16392kb
Test #25:
score: 0
Accepted
time: 117ms
memory: 15172kb
Test #26:
score: 0
Accepted
time: 136ms
memory: 16296kb
Test #27:
score: 0
Accepted
time: 114ms
memory: 15256kb
Test #28:
score: 0
Accepted
time: 124ms
memory: 15836kb
Test #29:
score: 0
Accepted
time: 3ms
memory: 5332kb
Test #30:
score: 0
Accepted
time: 1ms
memory: 3584kb
Test #31:
score: 0
Accepted
time: 0ms
memory: 5128kb
Test #32:
score: 0
Accepted
time: 0ms
memory: 5396kb
Test #33:
score: 0
Accepted
time: 1ms
memory: 3556kb
Test #34:
score: 0
Accepted
time: 1ms
memory: 3600kb
Test #35:
score: 0
Accepted
time: 1ms
memory: 3472kb
Test #36:
score: 0
Accepted
time: 1ms
memory: 3540kb
Test #37:
score: 0
Accepted
time: 0ms
memory: 3636kb
Test #38:
score: 0
Accepted
time: 1ms
memory: 3712kb
Test #39:
score: 0
Accepted
time: 1ms
memory: 3584kb
Test #40:
score: 0
Accepted
time: 1ms
memory: 3628kb
Test #41:
score: 0
Accepted
time: 9ms
memory: 4460kb
Test #42:
score: 0
Accepted
time: 8ms
memory: 4408kb
Test #43:
score: 0
Accepted
time: 8ms
memory: 4392kb
Test #44:
score: 0
Accepted
time: 9ms
memory: 4416kb
Test #45:
score: 0
Accepted
time: 8ms
memory: 4644kb
Test #46:
score: 0
Accepted
time: 8ms
memory: 4400kb
Test #47:
score: 0
Accepted
time: 32ms
memory: 6012kb
Test #48:
score: 0
Accepted
time: 40ms
memory: 6260kb
Test #49:
score: 0
Accepted
time: 39ms
memory: 6152kb
Test #50:
score: 0
Accepted
time: 30ms
memory: 5484kb
Test #51:
score: 0
Accepted
time: 24ms
memory: 5604kb
Test #52:
score: 0
Accepted
time: 31ms
memory: 5584kb
Test #53:
score: 0
Accepted
time: 71ms
memory: 6488kb
Test #54:
score: 0
Accepted
time: 76ms
memory: 6564kb
Test #55:
score: 0
Accepted
time: 72ms
memory: 6644kb
Test #56:
score: 0
Accepted
time: 62ms
memory: 6520kb
Test #57:
score: 0
Accepted
time: 66ms
memory: 6636kb
Test #58:
score: 0
Accepted
time: 65ms
memory: 6612kb
Test #59:
score: 0
Accepted
time: 1ms
memory: 3764kb
Test #60:
score: 0
Accepted
time: 4ms
memory: 5924kb
Test #61:
score: 0
Accepted
time: 2ms
memory: 3596kb
Test #62:
score: 0
Accepted
time: 0ms
memory: 3768kb