QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#507284#5511. Minor EvilNYCU_MyGO#WA 681ms5832kbC++206.0kb2024-08-06 15:18:482024-08-06 15:18:49

Judging History

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

  • [2024-08-06 15:18:49]
  • 评测
  • 测评结果:WA
  • 用时:681ms
  • 内存:5832kb
  • [2024-08-06 15:18:48]
  • 提交

answer

#ifndef NYCU_MyGO
#define NYCU_MyGO
#include NYCU_MyGO __FILE__ NYCU_MyGO

void solve() {
    int N, M; cin >> N >> M;
    
    vector<vector<pii>> adj(N+1);
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v;
        adj[u].eb(v, i);
    }
    
    int S; cin >> S;
    
    vector<int> kill(N+1, 0);
    for (int i = 0; i < S; ++i) {
        int s; cin >> s, kill[s] = 1;
    }
    
    string ans(M, 'N');
    
    vector<int> max_id(N+1, -1);
    Prior<pii> pq;
    for (int i = 1; i <= N; ++i) { if (!kill[i]) max_id[i] = M, pq.ee(M, i); }
    while (SZ(pq)) {
        auto [lst_id, now] = pq.top(); pq.pop();
        if (lst_id < max_id[now]) continue;
        for (auto [x, id] : adj[now]) {
            if (id < lst_id and chmax(max_id[x], id)) {
                ans[id] = 'T';
                pq.ee(max_id[x], x);
            }
        }
    }
    
    for (int i = 1; i <= N; ++i) {
        if (max_id[i] == -1) { cout << "NIE" << "\n"; return; }
    }
    cout << "TAK" << "\n";
    cout << ans << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1; cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
#define int i64
using f80 = long double;
#define dobule f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "\u001b[33m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }

#endif

/**
 *                                                                                                                 
 *                                                                                                                 
 *                                                                                                                 
 *                            iiiiii         iiiiiiiiii       iiiiiiiiiiiiii                                       
 *                       iiiiiiiiiiiii   iiiiiii    iiii    iiiiiiiiiiiiiii                          ii   iiii     
 *                    iiiiiiii     iiiiiiiii         iiii       iiii iii              iii          iiiiiiiiii      
 *                 iiiiiii          iiiiii           iiii    iiii   ii           iiiiiiiiii      iiii iiii         
 *               iiiiii            iiiii             iiii iiii        iii      iiii    iiiiiiiiiiiiiiiii  ii       
 *             iiiiii            iiiiiii            iiiiiii       iiiiiiii   iii    iiiiiiiiiiiiii iii  iiii       
 *           iiiiii             iiiiiii            iiiii   ii   iiii       iiiiiiiiiii iiii  iii iiii iiii      iii
 *          iiiii              iiiiiiii       ii        iiiii iiii    iiiiiiiii        iii iii  iii  iii  ii  iiii 
 *        iiiiii              iiiiiiii      iiiii     iiiii iiiiiiiiiiiiiiii         iii  iii  ii  iii  iii iiii   
 *       iiiii                 iiiiii     iiii     iiiiii iiiiiii    iii iii       iiii  ii   i   ii  iii  iii     
 *     iiiiii                            iiii  iiiiiiiiiiiiiii       iii iiii   iiiii  iii  ii  iii  iii  ii       
 *    iiiii                              iiiiiiii iiiiiiiiii       iiii   iiiiiiiii            ii  iii  ii         
 *   iiiii                                     iiiiii  iiii      iiiii              iii      ii   ii  i            
 * iiiiii                                  iiiiiiii   iiiii    iiiii                        ii  ii   ii            
 * iiiii                                iiii  iiii    iiiiiiiiiiii                             ii                  
 *  iii                              iiii   iiii       iiiiiiii                                                    
 *                                iiiii   iiii                                                                     
 *                              iiii     iiii                                                                      
 *                            iiii    iiiii                                                                        
 *                          iii     iiiii                                                                          
 *                        iii     iiiii                                                                            
 *                       iii   iiiiii                                                                              
 *                       iiiiiiiii                                                                                 
 *                       iiiiii                                                                                    
 *                                                                                                                 
 *                                                                                                                 
 *                                                                                                                 
**/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3752kb

input:

2
5 6
1 2
2 1
2 5
2 3
2 4
4 2
3
1 2 3
3 2
1 2
2 3
2
2 3

output:

TAK
NTNTNT
NIE

result:

ok correct (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 681ms
memory: 5832kb

input:

1000
5 6
1 2
2 1
2 5
2 3
2 4
4 2
3
1 2 3
3 2
1 2
2 3
2
2 3
2 1
1 2
1
1
2 1
1 2
1
2
3 3
2 1
3 2
3 2
1
3
3 3
1 3
1 3
1 2
2
1 3
3 3
1 2
1 3
1 3
1
2
3 3
2 1
2 3
1 3
1
2
3 3
3 2
3 1
1 2
3
1 2 3
3 3
1 2
2 3
1 2
1
3
3 3
2 1
1 2
1 2
1
2
3 3
2 1
1 3
1 3
1
1
3 3
3 2
3 2
2 3
1
3
3 3
3 2
1 2
2 1
1
1
3 3
2 1
3 2...

output:

TAK
NTNTNT
NIE
NIE
TAK
T
NIE
NIE
TAK
TNN
NIE
NIE
TAK
NTN
TAK
NTT
TAK
TNN
TAK
NNT
TAK
NNT
TAK
TNT
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
TAK
TTNN
TAK
TNTN
NIE
NIE
NIE
NIE
NIE
NIE
NIE
TAK
TNTN
TAK
NTTN
TAK
TNTT
TAK
TNTN
NIE
TAK
NTTN
NIE
NIE
TAK
NTNT
NIE
TAK
TTTN
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
TAK
TNT
NI...

result:

wrong answer Some poeple who should be dead are alive. (test case 93)