QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#372059#2428. Comma Sprinklercciafrino#AC ✓149ms18776kbC++201.9kb2024-03-30 20:40:112024-03-30 20:40:12

Judging History

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

  • [2024-03-30 20:40:12]
  • 评测
  • 测评结果:AC
  • 用时:149ms
  • 内存:18776kb
  • [2024-03-30 20:40:11]
  • 提交

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';
}

详细

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