oj.uz

답안 #534021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534021 2022-03-07T19:44:19 Z Evang Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 906 ms 213056 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int N = 1e5+5;
const int bsz = 250;
int n, m, q;
vi adj[N];  // reversed adj
vpi fur[N];

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n >> m >> q;
    while(m--){
        int x, y;
        cin >> x >> y;
        adj[y].pb(x);
    }

    // calc fur[]
    for(int i = 1; i <= n; ++i){
        fur[i].eb(0, i);
        for(int j: adj[i]){
            vpi ans;

            vc<bool> vis(i+1);
            int p = 0, p2 = 0;
            while((p < ssize(fur[i]) || p2 < ssize(fur[j]))&&ssize(ans)<bsz){
                if(p2>=ssize(fur[j])||p<ssize(fur[i])
                                                   &&fur[i][p].ff>fur[j][p2].ff+1){
                    if(!vis[fur[i][p].ss]){
                        ans.pb(fur[i][p]);
                        vis[fur[i][p].ss] = 1;
                    }
                    ++p;
                }else{
                    if(!vis[fur[j][p2].ss]){
                        ans.eb(fur[j][p2].ff+1, fur[j][p2].ss);
                        vis[fur[j][p2].ss] = 1;
                    }
                    ++p2;
                }
            }
            swap(fur[i], ans);
        }
    }

    // print fur[]
#ifdef _DEBUG
    clog << "Line " << __LINE__ << ":\n";
    for(int i = 1; i <= n; ++i) {
        for (auto [d, v]: fur[i])
            clog << '(' << d << ", " << v << ") ";
        clog << el;
    }
    clog << el;
#endif

    while(q--){
        int t, y;
        cin >> t >> y;
        vi busy;
        for(int i = 0; i < y; ++i){
            int x;
            cin >> x;
            busy.pb(x);
        }
        sort(all(busy));

        if(y<bsz){
            for(auto[d, v]: fur[t])
                if(!bs(all(busy), v)){
                    cout << d << el;
                    goto next_query;
                }
            cout << -1 << el;
        }else{
            // naive dp
            vi dp(t+1);
            for(int i = 1; i <= t; ++i){
                if(bs(all(busy), i))
                    dp[i] = -inf;
                for(int j: adj[i])
                    dp[i] = max(dp[i], dp[j]+1);
            }

            if(dp[t]<0)
                cout << -1 << el;
            else
                cout << dp[t] << el;
        }

    next_query:;
    }
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:97:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   96 |                 if(p2>=ssize(fur[j])||p<ssize(fur[i])
      |                                       ~~~~~~~~~~~~~~~
   97 |                                                    &&fur[i][p].ff>fur[j][p2].ff+1){
      |                                                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 6 ms 5444 KB Output is correct
6 Correct 5 ms 5416 KB Output is correct
7 Correct 5 ms 5452 KB Output is correct
8 Correct 8 ms 6860 KB Output is correct
9 Correct 7 ms 6860 KB Output is correct
10 Correct 8 ms 6860 KB Output is correct
11 Correct 8 ms 6692 KB Output is correct
12 Correct 6 ms 6220 KB Output is correct
13 Correct 8 ms 6732 KB Output is correct
14 Correct 7 ms 6132 KB Output is correct
15 Correct 6 ms 5580 KB Output is correct
16 Correct 7 ms 6048 KB Output is correct
17 Correct 7 ms 6284 KB Output is correct
18 Correct 6 ms 5836 KB Output is correct
19 Correct 7 ms 6308 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 6 ms 5444 KB Output is correct
6 Correct 5 ms 5416 KB Output is correct
7 Correct 5 ms 5452 KB Output is correct
8 Correct 8 ms 6860 KB Output is correct
9 Correct 7 ms 6860 KB Output is correct
10 Correct 8 ms 6860 KB Output is correct
11 Correct 8 ms 6692 KB Output is correct
12 Correct 6 ms 6220 KB Output is correct
13 Correct 8 ms 6732 KB Output is correct
14 Correct 7 ms 6132 KB Output is correct
15 Correct 6 ms 5580 KB Output is correct
16 Correct 7 ms 6048 KB Output is correct
17 Correct 7 ms 6284 KB Output is correct
18 Correct 6 ms 5836 KB Output is correct
19 Correct 7 ms 6308 KB Output is correct
20 Correct 405 ms 9168 KB Output is correct
21 Correct 391 ms 9320 KB Output is correct
22 Correct 420 ms 9476 KB Output is correct
23 Correct 427 ms 9284 KB Output is correct
24 Correct 550 ms 152512 KB Output is correct
25 Correct 562 ms 157352 KB Output is correct
26 Correct 556 ms 157260 KB Output is correct
27 Correct 556 ms 213056 KB Output is correct
28 Correct 550 ms 212252 KB Output is correct
29 Correct 554 ms 212348 KB Output is correct
30 Correct 557 ms 211940 KB Output is correct
31 Correct 556 ms 206896 KB Output is correct
32 Correct 543 ms 212036 KB Output is correct
33 Correct 467 ms 133300 KB Output is correct
34 Correct 435 ms 114904 KB Output is correct
35 Correct 466 ms 132616 KB Output is correct
36 Correct 517 ms 172720 KB Output is correct
37 Correct 506 ms 160220 KB Output is correct
38 Correct 524 ms 172968 KB Output is correct

Subtask #3
86.0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 6 ms 5444 KB Output is correct
6 Correct 5 ms 5416 KB Output is correct
7 Correct 5 ms 5452 KB Output is correct
8 Correct 8 ms 6860 KB Output is correct
9 Correct 7 ms 6860 KB Output is correct
10 Correct 8 ms 6860 KB Output is correct
11 Correct 8 ms 6692 KB Output is correct
12 Correct 6 ms 6220 KB Output is correct
13 Correct 8 ms 6732 KB Output is correct
14 Correct 7 ms 6132 KB Output is correct
15 Correct 6 ms 5580 KB Output is correct
16 Correct 7 ms 6048 KB Output is correct
17 Correct 7 ms 6284 KB Output is correct
18 Correct 6 ms 5836 KB Output is correct
19 Correct 7 ms 6308 KB Output is correct
20 Correct 405 ms 9168 KB Output is correct
21 Correct 391 ms 9320 KB Output is correct
22 Correct 420 ms 9476 KB Output is correct
23 Correct 427 ms 9284 KB Output is correct
24 Correct 550 ms 152512 KB Output is correct
25 Correct 562 ms 157352 KB Output is correct
26 Correct 556 ms 157260 KB Output is correct
27 Correct 556 ms 213056 KB Output is correct
28 Correct 550 ms 212252 KB Output is correct
29 Correct 554 ms 212348 KB Output is correct
30 Correct 557 ms 211940 KB Output is correct
31 Correct 556 ms 206896 KB Output is correct
32 Correct 543 ms 212036 KB Output is correct
33 Correct 467 ms 133300 KB Output is correct
34 Correct 435 ms 114904 KB Output is correct
35 Correct 466 ms 132616 KB Output is correct
36 Correct 517 ms 172720 KB Output is correct
37 Correct 506 ms 160220 KB Output is correct
38 Correct 524 ms 172968 KB Output is correct
39 Correct 586 ms 152744 KB Output is correct
40 Correct 556 ms 154180 KB Output is correct
41 Correct 564 ms 154460 KB Output is correct
42 Correct 752 ms 154840 KB Output is correct
43 Correct 567 ms 153688 KB Output is correct
44 Correct 444 ms 9428 KB Output is correct
45 Correct 419 ms 9028 KB Output is correct
46 Correct 401 ms 8780 KB Output is correct
47 Correct 422 ms 8716 KB Output is correct
48 Correct 403 ms 8516 KB Output is correct
49 Correct 649 ms 212152 KB Output is correct
50 Correct 618 ms 211224 KB Output is correct
51 Correct 417 ms 8868 KB Output is correct
52 Correct 376 ms 8252 KB Output is correct
53 Correct 554 ms 171572 KB Output is correct
54 Correct 545 ms 159656 KB Output is correct
55 Correct 523 ms 171172 KB Output is correct
56 Correct 505 ms 159992 KB Output is correct
57 Correct 431 ms 9036 KB Output is correct
58 Correct 472 ms 8816 KB Output is correct
59 Correct 412 ms 8328 KB Output is correct
60 Correct 414 ms 8260 KB Output is correct
61 Correct 671 ms 211736 KB Output is correct
62 Correct 652 ms 172404 KB Output is correct
63 Correct 689 ms 159400 KB Output is correct
64 Correct 906 ms 211976 KB Output is correct
65 Correct 885 ms 171808 KB Output is correct
66 Correct 863 ms 160532 KB Output is correct
67 Correct 637 ms 211280 KB Output is correct
68 Correct 524 ms 171992 KB Output is correct
69 Correct 529 ms 157972 KB Output is correct
70 Correct 609 ms 211864 KB Output is correct
71 Correct 570 ms 172368 KB Output is correct
72 Correct 541 ms 159936 KB Output is correct
73 Correct 601 ms 211680 KB Output is correct
74 Correct 578 ms 172352 KB Output is correct
75 Correct 555 ms 159764 KB Output is correct
76 Correct 645 ms 211848 KB Output is correct
77 Correct 625 ms 211264 KB Output is correct
78 Correct 577 ms 211680 KB Output is correct
79 Correct 401 ms 8684 KB Output is correct
80 Correct 410 ms 8400 KB Output is correct
81 Correct 352 ms 8132 KB Output is correct
82 Correct 641 ms 211460 KB Output is correct
83 Correct 664 ms 206020 KB Output is correct
84 Correct 612 ms 210956 KB Output is correct
85 Correct 617 ms 205468 KB Output is correct
86 Correct 592 ms 211480 KB Output is correct
87 Correct 598 ms 206500 KB Output is correct
88 Correct 426 ms 8560 KB Output is correct
89 Correct 439 ms 8488 KB Output is correct
90 Correct 410 ms 8124 KB Output is correct
91 Correct 451 ms 8180 KB Output is correct
92 Correct 410 ms 7996 KB Output is correct
93 Correct 418 ms 8088 KB Output is correct
94 Correct 501 ms 132812 KB Output is correct
95 Correct 480 ms 113348 KB Output is correct
96 Correct 465 ms 131600 KB Output is correct
97 Correct 444 ms 114956 KB Output is correct
98 Correct 491 ms 132504 KB Output is correct
99 Correct 443 ms 115140 KB Output is correct
100 Correct 463 ms 8528 KB Output is correct
101 Correct 434 ms 8760 KB Output is correct
102 Correct 431 ms 8140 KB Output is correct
103 Correct 420 ms 8080 KB Output is correct
104 Correct 431 ms 8028 KB Output is correct
105 Correct 415 ms 8072 KB Output is correct
106 Correct 555 ms 171180 KB Output is correct
107 Correct 541 ms 159540 KB Output is correct
108 Correct 526 ms 171740 KB Output is correct
109 Correct 512 ms 158888 KB Output is correct
110 Correct 543 ms 172384 KB Output is correct
111 Correct 530 ms 160220 KB Output is correct
112 Correct 429 ms 8532 KB Output is correct
113 Correct 453 ms 8516 KB Output is correct
114 Correct 402 ms 8132 KB Output is correct
115 Correct 420 ms 8160 KB Output is correct
116 Correct 426 ms 8120 KB Output is correct
117 Correct 426 ms 7956 KB Output is correct
118 Correct 626 ms 210960 KB Output is correct
119 Correct 539 ms 171784 KB Output is correct
120 Correct 519 ms 158856 KB Output is correct
121 Correct 628 ms 211020 KB Output is correct
122 Correct 521 ms 170924 KB Output is correct
123 Correct 503 ms 158404 KB Output is correct
124 Correct 597 ms 210848 KB Output is correct
125 Correct 521 ms 171952 KB Output is correct
126 Correct 498 ms 158196 KB Output is correct