oj.uz

Submission #203052

# Submission time Handle Problem Language Result Execution time Memory
203052 2020-02-19T05:20:10 Z Rakhmand Bitaro’s Party (JOI18_bitaro) C++14
100 / 100
 1802 ms 113952 KB 
//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)

const int MXN = 1e5 + 1;
const long long MNN = 1e6 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 500;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

void istxt(bool yes){
    if(yes == 1){
        freopen("balancing.in", "r", stdin);
        //freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/e.txt", "w", stdout);
    }else{
        freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
    }
}

int n, q, m, dp[MXN], lol[MXN], sq = 69;
vector<int> g[MXN];
vector<pair<int, int> > best[MXN], ans[MXN];
bool visit[MXN];

int main () {
    ios;
    //istxt(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        g[v].pb(u);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < g[i].size(); j++){
            int last = g[i][j];
            for(int e = 0; e < ans[last].size(); e++){
                int cost = ans[last][e].F, pos = ans[last][e].S;
                lol[pos] = max(lol[pos], cost + 1);
            }
        }
        for(int j = 0; j < g[i].size(); j++){
            int last = g[i][j];
            for(int e = 0; e < ans[last].size(); e++){
                int pos = ans[last][e].S;
                if(lol[pos] != -1){
                    ans[i].push_back({lol[pos], pos});
                    lol[pos] = -1;
                }
            }
        }
        ans[i].push_back({0, i});
        sort(ans[i].begin(), ans[i].end(), greater<pair<int, int> >());
        while(ans[i].size() > sq){
            ans[i].pop_back();
        }
    }
    while(q--){
        int x, k;
        cin >> x >> k;
        vector<int> keks;
        for(int i = 0; i < k; i++){
            int u;
            cin >> u;
            keks.push_back(u);
            visit[u] = 1;
        }
        if(k >= sq){
            for(int i = x; i >= 1; i--){
                dp[i] = -OO;
            }
            dp[x] = 0;
            int res = -1;
            for(int i = x; i >= 1; i--){
                if(dp[i] < 0) continue;
                if(dp[i] > res && visit[i] == 0) res = dp[i];
                for(int j = 0; j < g[i].size(); j++) dp[g[i][j]] = max(dp[g[i][j]], dp[i] + 1);
            }
            cout << res << nl;
        }else{
            int res = -1;
            for(int i = 0; i < ans[x].size(); i++){
                if(visit[ans[x][i].S] == 0){
                    res = ans[x][i].F;
                    break;
                }
            }
            cout << res << nl;
        }
        for(int i = 0; i < keks.size(); i++){
            visit[keks[i]] = 0;
        }
    }
    return 0;
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:77:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[i].size(); j++){
                        ~~^~~~~~~~~~~~~
bitaro.cpp:79:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int e = 0; e < ans[last].size(); e++){
                            ~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:84:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[i].size(); j++){
                        ~~^~~~~~~~~~~~~
bitaro.cpp:86:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int e = 0; e < ans[last].size(); e++){
                            ~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:96:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ans[i].size() > sq){
               ~~~~~~~~~~~~~~^~~~
bitaro.cpp:119:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j = 0; j < g[i].size(); j++) dp[g[i][j]] = max(dp[g[i][j]], dp[i] + 1);
                                ~~^~~~~~~~~~~~~
bitaro.cpp:124:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < ans[x].size(); i++){
                            ~~^~~~~~~~~~~~~~~
bitaro.cpp:132:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < keks.size(); i++){
                        ~~^~~~~~~~~~~~~
bitaro.cpp: In function 'void istxt(bool)':
bitaro.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("balancing.in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 11 ms 7416 KB Output is correct
4 Correct 9 ms 7420 KB Output is correct
5 Correct 12 ms 7800 KB Output is correct
6 Correct 12 ms 7928 KB Output is correct
7 Correct 12 ms 7800 KB Output is correct
8 Correct 13 ms 8440 KB Output is correct
9 Correct 13 ms 8440 KB Output is correct
10 Correct 13 ms 8440 KB Output is correct
11 Correct 14 ms 8312 KB Output is correct
12 Correct 13 ms 8184 KB Output is correct
13 Correct 15 ms 8312 KB Output is correct
14 Correct 13 ms 7928 KB Output is correct
15 Correct 13 ms 7928 KB Output is correct
16 Correct 13 ms 8056 KB Output is correct
17 Correct 14 ms 8184 KB Output is correct
18 Correct 15 ms 7928 KB Output is correct
19 Correct 16 ms 8184 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 11 ms 7416 KB Output is correct
4 Correct 9 ms 7420 KB Output is correct
5 Correct 12 ms 7800 KB Output is correct
6 Correct 12 ms 7928 KB Output is correct
7 Correct 12 ms 7800 KB Output is correct
8 Correct 13 ms 8440 KB Output is correct
9 Correct 13 ms 8440 KB Output is correct
10 Correct 13 ms 8440 KB Output is correct
11 Correct 14 ms 8312 KB Output is correct
12 Correct 13 ms 8184 KB Output is correct
13 Correct 15 ms 8312 KB Output is correct
14 Correct 13 ms 7928 KB Output is correct
15 Correct 13 ms 7928 KB Output is correct
16 Correct 13 ms 8056 KB Output is correct
17 Correct 14 ms 8184 KB Output is correct
18 Correct 15 ms 7928 KB Output is correct
19 Correct 16 ms 8184 KB Output is correct
20 Correct 118 ms 9464 KB Output is correct
21 Correct 113 ms 9464 KB Output is correct
22 Correct 117 ms 9464 KB Output is correct
23 Correct 133 ms 9548 KB Output is correct
24 Correct 617 ms 89744 KB Output is correct
25 Correct 598 ms 91384 KB Output is correct
26 Correct 610 ms 91056 KB Output is correct
27 Correct 455 ms 113884 KB Output is correct
28 Correct 478 ms 113840 KB Output is correct
29 Correct 466 ms 113952 KB Output is correct
30 Correct 465 ms 113920 KB Output is correct
31 Correct 589 ms 113236 KB Output is correct
32 Correct 488 ms 113412 KB Output is correct
33 Correct 399 ms 76244 KB Output is correct
34 Correct 548 ms 89044 KB Output is correct
35 Correct 397 ms 75768 KB Output is correct
36 Correct 439 ms 94836 KB Output is correct
37 Correct 577 ms 92416 KB Output is correct
38 Correct 432 ms 94716 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 11 ms 7416 KB Output is correct
4 Correct 9 ms 7420 KB Output is correct
5 Correct 12 ms 7800 KB Output is correct
6 Correct 12 ms 7928 KB Output is correct
7 Correct 12 ms 7800 KB Output is correct
8 Correct 13 ms 8440 KB Output is correct
9 Correct 13 ms 8440 KB Output is correct
10 Correct 13 ms 8440 KB Output is correct
11 Correct 14 ms 8312 KB Output is correct
12 Correct 13 ms 8184 KB Output is correct
13 Correct 15 ms 8312 KB Output is correct
14 Correct 13 ms 7928 KB Output is correct
15 Correct 13 ms 7928 KB Output is correct
16 Correct 13 ms 8056 KB Output is correct
17 Correct 14 ms 8184 KB Output is correct
18 Correct 15 ms 7928 KB Output is correct
19 Correct 16 ms 8184 KB Output is correct
20 Correct 118 ms 9464 KB Output is correct
21 Correct 113 ms 9464 KB Output is correct
22 Correct 117 ms 9464 KB Output is correct
23 Correct 133 ms 9548 KB Output is correct
24 Correct 617 ms 89744 KB Output is correct
25 Correct 598 ms 91384 KB Output is correct
26 Correct 610 ms 91056 KB Output is correct
27 Correct 455 ms 113884 KB Output is correct
28 Correct 478 ms 113840 KB Output is correct
29 Correct 466 ms 113952 KB Output is correct
30 Correct 465 ms 113920 KB Output is correct
31 Correct 589 ms 113236 KB Output is correct
32 Correct 488 ms 113412 KB Output is correct
33 Correct 399 ms 76244 KB Output is correct
34 Correct 548 ms 89044 KB Output is correct
35 Correct 397 ms 75768 KB Output is correct
36 Correct 439 ms 94836 KB Output is correct
37 Correct 577 ms 92416 KB Output is correct
38 Correct 432 ms 94716 KB Output is correct
39 Correct 708 ms 90220 KB Output is correct
40 Correct 623 ms 89860 KB Output is correct
41 Correct 698 ms 90528 KB Output is correct
42 Correct 645 ms 90556 KB Output is correct
43 Correct 637 ms 90040 KB Output is correct
44 Correct 173 ms 10512 KB Output is correct
45 Correct 130 ms 10132 KB Output is correct
46 Correct 429 ms 10104 KB Output is correct
47 Correct 153 ms 10048 KB Output is correct
48 Correct 119 ms 10104 KB Output is correct
49 Correct 532 ms 113144 KB Output is correct
50 Correct 1802 ms 112992 KB Output is correct
51 Correct 157 ms 10232 KB Output is correct
52 Correct 451 ms 9824 KB Output is correct
53 Correct 519 ms 93824 KB Output is correct
54 Correct 644 ms 90592 KB Output is correct
55 Correct 1227 ms 93944 KB Output is correct
56 Correct 1031 ms 91640 KB Output is correct
57 Correct 149 ms 10104 KB Output is correct
58 Correct 148 ms 10104 KB Output is correct
59 Correct 452 ms 9720 KB Output is correct
60 Correct 432 ms 9796 KB Output is correct
61 Correct 625 ms 112792 KB Output is correct
62 Correct 552 ms 93928 KB Output is correct
63 Correct 633 ms 90616 KB Output is correct
64 Correct 880 ms 112928 KB Output is correct
65 Correct 685 ms 94328 KB Output is correct
66 Correct 704 ms 91348 KB Output is correct
67 Correct 1142 ms 113400 KB Output is correct
68 Correct 842 ms 94840 KB Output is correct
69 Correct 842 ms 91492 KB Output is correct
70 Correct 504 ms 113376 KB Output is correct
71 Correct 473 ms 94492 KB Output is correct
72 Correct 584 ms 91096 KB Output is correct
73 Correct 528 ms 113400 KB Output is correct
74 Correct 495 ms 94456 KB Output is correct
75 Correct 623 ms 93144 KB Output is correct
76 Correct 537 ms 113632 KB Output is correct
77 Correct 1334 ms 113484 KB Output is correct
78 Correct 475 ms 113320 KB Output is correct
79 Correct 160 ms 10104 KB Output is correct
80 Correct 341 ms 9844 KB Output is correct
81 Correct 115 ms 9720 KB Output is correct
82 Correct 579 ms 113144 KB Output is correct
83 Correct 671 ms 112376 KB Output is correct
84 Correct 1089 ms 112760 KB Output is correct
85 Correct 1002 ms 113400 KB Output is correct
86 Correct 466 ms 113024 KB Output is correct
87 Correct 579 ms 112160 KB Output is correct
88 Correct 153 ms 9848 KB Output is correct
89 Correct 156 ms 9824 KB Output is correct
90 Correct 341 ms 9464 KB Output is correct
91 Correct 338 ms 9592 KB Output is correct
92 Correct 120 ms 9592 KB Output is correct
93 Correct 115 ms 9488 KB Output is correct
94 Correct 472 ms 75768 KB Output is correct
95 Correct 633 ms 92792 KB Output is correct
96 Correct 853 ms 75384 KB Output is correct
97 Correct 889 ms 93176 KB Output is correct
98 Correct 399 ms 75960 KB Output is correct
99 Correct 550 ms 90656 KB Output is correct
100 Correct 161 ms 9976 KB Output is correct
101 Correct 156 ms 9848 KB Output is correct
102 Correct 274 ms 9464 KB Output is correct
103 Correct 276 ms 9608 KB Output is correct
104 Correct 118 ms 9464 KB Output is correct
105 Correct 123 ms 9464 KB Output is correct
106 Correct 509 ms 93820 KB Output is correct
107 Correct 645 ms 91256 KB Output is correct
108 Correct 904 ms 94200 KB Output is correct
109 Correct 813 ms 90360 KB Output is correct
110 Correct 437 ms 94500 KB Output is correct
111 Correct 559 ms 91000 KB Output is correct
112 Correct 154 ms 9848 KB Output is correct
113 Correct 156 ms 9848 KB Output is correct
114 Correct 327 ms 9592 KB Output is correct
115 Correct 337 ms 9596 KB Output is correct
116 Correct 120 ms 9464 KB Output is correct
117 Correct 119 ms 9464 KB Output is correct
118 Correct 478 ms 112352 KB Output is correct
119 Correct 440 ms 93640 KB Output is correct
120 Correct 601 ms 92332 KB Output is correct
121 Correct 479 ms 112504 KB Output is correct
122 Correct 464 ms 93432 KB Output is correct
123 Correct 587 ms 91128 KB Output is correct
124 Correct 501 ms 112760 KB Output is correct
125 Correct 473 ms 94328 KB Output is correct
126 Correct 574 ms 91896 KB Output is correct