QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#375281#2428. Comma SprinklerUFRJAC ✓299ms26232kbC++201.7kb2024-04-03 04:45:112024-04-03 04:45:13

Judging History

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

  • [2024-04-03 04:45:13]
  • 评测
  • 测评结果:AC
  • 用时:299ms
  • 内存:26232kb
  • [2024-04-03 04:45:11]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

struct dsu_t{
    vector<int> par;
    dsu_t(int n) : par(n, -1) {}
    int find(int v){
        if(par[v] < 0) return v;
        else return par[v] = find(par[v]);
    }
    bool same_set(int a, int b){
        return find(a) == find(b);
    }
    void unite(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return;
        par[b] = a;
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(false);
    string line, s;
    getline(cin, line);
    istringstream is(line);
    vector<pair<string, char>> text;
    vector<string> v;
    vector<char> after;
    while(is>>s){
        char a = '!';
        if(s.back() == ',' || s.back() == '.'){
            a = s.back();
            s.pop_back();
        }
        v.push_back(s);
        after.push_back(a);
    }
    const int n = v.size();
    map<string, int> get_id;
    int id = 2;
    for(string s : v){
        if(!get_id.count(s)){
            get_id[s] = id;
            id += 2;
        }
    }
    dsu_t uf(id);
    for(int i = 1; i < n; i++){
        int a = get_id[v[i-1]] + 1;
        int b = get_id[v[i]];
        if(after[i-1] != '.')
            uf.unite(a, b);
        if(after[i-1] == ','){
            uf.unite(1, a);
            uf.unite(1, b);
        }
    }
    string ans;
    for(int i =0; i<n; i++){
        ans += v[i];
        if(after[i] != '!'){
            ans += after[i];
        } else{
            int x = get_id[v[i]] + 1;
            if(uf.same_set(x, 1))
                ans += ',';
        }
        ans += ' ';
    }
    cout<<ans<<"\n";
    
    return 0;
}

Details

Test #1:

score: 100
Accepted
time: 1ms
memory: 3628kb

Test #2:

score: 0
Accepted
time: 1ms
memory: 3540kb

Test #3:

score: 0
Accepted
time: 0ms
memory: 3596kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 3572kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 3504kb

Test #6:

score: 0
Accepted
time: 31ms
memory: 25032kb

Test #7:

score: 0
Accepted
time: 115ms
memory: 24188kb

Test #8:

score: 0
Accepted
time: 116ms
memory: 23836kb

Test #9:

score: 0
Accepted
time: 1ms
memory: 3588kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 3656kb

Test #11:

score: 0
Accepted
time: 1ms
memory: 3880kb

Test #12:

score: 0
Accepted
time: 0ms
memory: 3596kb

Test #13:

score: 0
Accepted
time: 1ms
memory: 3872kb

Test #14:

score: 0
Accepted
time: 1ms
memory: 3876kb

Test #15:

score: 0
Accepted
time: 0ms
memory: 3564kb

Test #16:

score: 0
Accepted
time: 125ms
memory: 23668kb

Test #17:

score: 0
Accepted
time: 199ms
memory: 22796kb

Test #18:

score: 0
Accepted
time: 276ms
memory: 24988kb

Test #19:

score: 0
Accepted
time: 1ms
memory: 3828kb

Test #20:

score: 0
Accepted
time: 299ms
memory: 26232kb

Test #21:

score: 0
Accepted
time: 258ms
memory: 26076kb

Test #22:

score: 0
Accepted
time: 215ms
memory: 24600kb

Test #23:

score: 0
Accepted
time: 20ms
memory: 12116kb

Test #24:

score: 0
Accepted
time: 235ms
memory: 24160kb

Test #25:

score: 0
Accepted
time: 178ms
memory: 24048kb

Test #26:

score: 0
Accepted
time: 232ms
memory: 24264kb

Test #27:

score: 0
Accepted
time: 168ms
memory: 23552kb

Test #28:

score: 0
Accepted
time: 209ms
memory: 23784kb

Test #29:

score: 0
Accepted
time: 0ms
memory: 9436kb

Test #30:

score: 0
Accepted
time: 0ms
memory: 3556kb

Test #31:

score: 0
Accepted
time: 4ms
memory: 8164kb

Test #32:

score: 0
Accepted
time: 0ms
memory: 8840kb

Test #33:

score: 0
Accepted
time: 1ms
memory: 3596kb

Test #34:

score: 0
Accepted
time: 0ms
memory: 3876kb

Test #35:

score: 0
Accepted
time: 0ms
memory: 3560kb

Test #36:

score: 0
Accepted
time: 0ms
memory: 3540kb

Test #37:

score: 0
Accepted
time: 0ms
memory: 3540kb

Test #38:

score: 0
Accepted
time: 0ms
memory: 3580kb

Test #39:

score: 0
Accepted
time: 0ms
memory: 3564kb

Test #40:

score: 0
Accepted
time: 0ms
memory: 3644kb

Test #41:

score: 0
Accepted
time: 13ms
memory: 4880kb

Test #42:

score: 0
Accepted
time: 14ms
memory: 4784kb

Test #43:

score: 0
Accepted
time: 9ms
memory: 4920kb

Test #44:

score: 0
Accepted
time: 13ms
memory: 4924kb

Test #45:

score: 0
Accepted
time: 13ms
memory: 4956kb

Test #46:

score: 0
Accepted
time: 13ms
memory: 4880kb

Test #47:

score: 0
Accepted
time: 76ms
memory: 10980kb

Test #48:

score: 0
Accepted
time: 76ms
memory: 11040kb

Test #49:

score: 0
Accepted
time: 68ms
memory: 11192kb

Test #50:

score: 0
Accepted
time: 42ms
memory: 9176kb

Test #51:

score: 0
Accepted
time: 50ms
memory: 9052kb

Test #52:

score: 0
Accepted
time: 51ms
memory: 9776kb

Test #53:

score: 0
Accepted
time: 142ms
memory: 17476kb

Test #54:

score: 0
Accepted
time: 135ms
memory: 17584kb

Test #55:

score: 0
Accepted
time: 132ms
memory: 17504kb

Test #56:

score: 0
Accepted
time: 128ms
memory: 15464kb

Test #57:

score: 0
Accepted
time: 126ms
memory: 15940kb

Test #58:

score: 0
Accepted
time: 127ms
memory: 15352kb

Test #59:

score: 0
Accepted
time: 1ms
memory: 3504kb

Test #60:

score: 0
Accepted
time: 0ms
memory: 9884kb

Test #61:

score: 0
Accepted
time: 4ms
memory: 7604kb

Test #62:

score: 0
Accepted
time: 0ms
memory: 3592kb