QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#228013#6394. Turn on the LightkiwiHM#TL 0ms0kbC++141.5kb2023-10-28 10:39:572023-10-28 10:39:57

Judging History

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

  • [2023-10-28 10:39:57]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-10-28 10:39:57]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int n;
int dep[maxn];
vector<pair<int, int> >  ans;
vector<int> vec[3], tree[maxn];

inline void dfs(int u, int d){
    dep[u] = d;
    for(auto v: tree[u]) dfs(v, d + 1);
    return;
}

int main(){
    scanf("%d", &n);
    for(int it = 1; it < n; ++it){
        int i, p; scanf("%d%d", &i, &p); --i, --p;
        char buf[15]; scanf("%s", buf);
        tree[p].push_back(i);
        if(buf[0] == 'D') vec[0].push_back(i);
        else if(buf[0] == 'T') vec[1].push_back(i);
        else if(buf[0] == 'C') vec[2].push_back(i);
    }

    dfs(0, 0);

    for(int t = 0; t < 3; ++t) sort(vec[t].begin(), vec[t].end(), [&](const int &i, const int &j){ return dep[i] < dep[j]; });

    if(vec[1].size() % 2 == 1){
        puts("NO");
        return 0;
    }
    for(int i = 0; i < vec[1].size(); i += 2){
        if(dep[vec[1][i]] != dep[vec[1][i + 1]]){
            puts("NO");
            return 0;
        }
        ans.push_back(make_pair(vec[1][i], vec[1][i + 1]));
    }

    printf("shit %d %d\n", vec[0].size(), vec[2].size());

    if(vec[0].size() != vec[2].size()){
        puts("NO");
        return 0;
    }

    for(int i = 0; i < vec[0].size(); ++i){
        if(dep[vec[0][i]] >= dep[vec[2][i]]){
            puts("NO");
            return 0;
        }
        ans.push_back(make_pair(vec[0][i], vec[2][i]));
    }

    puts("YES");
    for(auto p: ans) printf("%d %d\n", p.first + 1, p.second + 1);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

3

output:


result: