oj.uz

Submission #703918

# Submission time Handle Problem Language Result Execution time Memory
703918 2023-02-28T20:42:00 Z igzi Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 859 ms 146368 KB 
#include <bits/stdc++.h>
#define D 103
#define maxN 100005
 
using namespace std;
 
vector <int> adj[maxN],u;
vector <pair<int,int>> d[maxN];
bool mar[maxN];
int n,m,q,i,j,x,y,t,ans,dp[maxN];
 
vector<pair<int,int>> dodaj(vector <pair<int,int>> a,vector <pair<int,int>> b){
vector<pair<int,int>> v;
int i,j;
i=j=0;
while(i<a.size() && j<b.size()){
    if(a[i].first>=b[j].first+1) {v.push_back(a[i]); i++;}
    else {v.push_back({b[j].first+1,b[j].second}); j++;}
}
while(i<a.size()){
    v.push_back(a[i]); i++;
}
while(j<b.size()){
    v.push_back({b[j].first+1,b[j].second}); j++;
}
vector<pair<int,int>> u;
for(i=0;i<v.size();i++){
if(!mar[v[i].second]){u.push_back(v[i]); mar[v[i].second]=true;}
}
for(i=0;i<u.size();i++) mar[u[i].second]=false;
while(u.size()>D) u.pop_back();
return u;
}
 
int main()
{
    srand(time(NULL));
    std::ios_base::sync_with_stdio(0);
    cin>>n>>m>>q;
    for(i=0;i<m;i++){
        cin>>x>>y;
        adj[y].push_back(x);
    }
    for(i=1;i<=n;i++){
        d[i].push_back({0,i});
        for(j=0;j<adj[i].size();j++){
            d[i]=dodaj(d[i],d[adj[i][j]]);
        }
    }
    while(q--){
        cin>>t>>x;
        u.clear();
        for(i=0;i<x;i++){
            cin>>y;
            mar[y]=true;
            u.push_back(y);
        }
        ans=-1;
        for(i=0;i<d[t].size();i++){
            if(!mar[d[t][i].second]){
                ans=d[t][i].first;
                break;
            }
        }
        if(x>=D && ans==-1)
        {
            for(i=1;i<=t;i++){
                dp[i]=-1;
                if(!mar[i]) dp[i]=0;
                for(j=0;j<adj[i].size();j++){
                    if(dp[adj[i][j]]!=-1) dp[i]=max(dp[i],dp[adj[i][j]]+1);
                }
            }
            ans=dp[t];
        }
        for(i=0;i<u.size();i++) mar[u[i]]=false;
        cout<<ans<<"\n";
    }
    return 0;
}

Compilation message

bitaro.cpp: In function 'std::vector<std::pair<int, int> > dodaj(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:16:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | while(i<a.size() && j<b.size()){
      |       ~^~~~~~~~~
bitaro.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | while(i<a.size() && j<b.size()){
      |                     ~^~~~~~~~~
bitaro.cpp:20:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | while(i<a.size()){
      |       ~^~~~~~~~~
bitaro.cpp:23:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | while(j<b.size()){
      |       ~^~~~~~~~~
bitaro.cpp:27:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 | for(i=0;i<v.size();i++){
      |         ~^~~~~~~~~
bitaro.cpp:30:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | for(i=0;i<u.size();i++) mar[u[i].second]=false;
      |         ~^~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(j=0;j<adj[i].size();j++){
      |                 ~^~~~~~~~~~~~~~
bitaro.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(i=0;i<d[t].size();i++){
      |                 ~^~~~~~~~~~~~
bitaro.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 for(j=0;j<adj[i].size();j++){
      |                         ~^~~~~~~~~~~~~~
bitaro.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(i=0;i<u.size();i++) mar[u[i]]=false;
      |                 ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 6 ms 5404 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 6 ms 5460 KB Output is correct
8 Correct 10 ms 5972 KB Output is correct
9 Correct 10 ms 5972 KB Output is correct
10 Correct 8 ms 6052 KB Output is correct
11 Correct 8 ms 6016 KB Output is correct
12 Correct 7 ms 5844 KB Output is correct
13 Correct 10 ms 5972 KB Output is correct
14 Correct 8 ms 5576 KB Output is correct
15 Correct 9 ms 5532 KB Output is correct
16 Correct 9 ms 5588 KB Output is correct
17 Correct 9 ms 5716 KB Output is correct
18 Correct 8 ms 5588 KB Output is correct
19 Correct 11 ms 5716 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 6 ms 5404 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 6 ms 5460 KB Output is correct
8 Correct 10 ms 5972 KB Output is correct
9 Correct 10 ms 5972 KB Output is correct
10 Correct 8 ms 6052 KB Output is correct
11 Correct 8 ms 6016 KB Output is correct
12 Correct 7 ms 5844 KB Output is correct
13 Correct 10 ms 5972 KB Output is correct
14 Correct 8 ms 5576 KB Output is correct
15 Correct 9 ms 5532 KB Output is correct
16 Correct 9 ms 5588 KB Output is correct
17 Correct 9 ms 5716 KB Output is correct
18 Correct 8 ms 5588 KB Output is correct
19 Correct 11 ms 5716 KB Output is correct
20 Correct 535 ms 7136 KB Output is correct
21 Correct 602 ms 7224 KB Output is correct
22 Correct 544 ms 7200 KB Output is correct
23 Correct 618 ms 7200 KB Output is correct
24 Correct 588 ms 108004 KB Output is correct
25 Correct 584 ms 100024 KB Output is correct
26 Correct 585 ms 99600 KB Output is correct
27 Correct 624 ms 110468 KB Output is correct
28 Correct 618 ms 110540 KB Output is correct
29 Correct 612 ms 110792 KB Output is correct
30 Correct 612 ms 110384 KB Output is correct
31 Correct 641 ms 132436 KB Output is correct
32 Correct 621 ms 110356 KB Output is correct
33 Correct 477 ms 73632 KB Output is correct
34 Correct 491 ms 88316 KB Output is correct
35 Correct 515 ms 73376 KB Output is correct
36 Correct 572 ms 91032 KB Output is correct
37 Correct 584 ms 111444 KB Output is correct
38 Correct 557 ms 91392 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 6 ms 5404 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 6 ms 5460 KB Output is correct
8 Correct 10 ms 5972 KB Output is correct
9 Correct 10 ms 5972 KB Output is correct
10 Correct 8 ms 6052 KB Output is correct
11 Correct 8 ms 6016 KB Output is correct
12 Correct 7 ms 5844 KB Output is correct
13 Correct 10 ms 5972 KB Output is correct
14 Correct 8 ms 5576 KB Output is correct
15 Correct 9 ms 5532 KB Output is correct
16 Correct 9 ms 5588 KB Output is correct
17 Correct 9 ms 5716 KB Output is correct
18 Correct 8 ms 5588 KB Output is correct
19 Correct 11 ms 5716 KB Output is correct
20 Correct 535 ms 7136 KB Output is correct
21 Correct 602 ms 7224 KB Output is correct
22 Correct 544 ms 7200 KB Output is correct
23 Correct 618 ms 7200 KB Output is correct
24 Correct 588 ms 108004 KB Output is correct
25 Correct 584 ms 100024 KB Output is correct
26 Correct 585 ms 99600 KB Output is correct
27 Correct 624 ms 110468 KB Output is correct
28 Correct 618 ms 110540 KB Output is correct
29 Correct 612 ms 110792 KB Output is correct
30 Correct 612 ms 110384 KB Output is correct
31 Correct 641 ms 132436 KB Output is correct
32 Correct 621 ms 110356 KB Output is correct
33 Correct 477 ms 73632 KB Output is correct
34 Correct 491 ms 88316 KB Output is correct
35 Correct 515 ms 73376 KB Output is correct
36 Correct 572 ms 91032 KB Output is correct
37 Correct 584 ms 111444 KB Output is correct
38 Correct 557 ms 91392 KB Output is correct
39 Correct 774 ms 109084 KB Output is correct
40 Correct 626 ms 101640 KB Output is correct
41 Correct 592 ms 105592 KB Output is correct
42 Correct 598 ms 102720 KB Output is correct
43 Correct 596 ms 108524 KB Output is correct
44 Correct 677 ms 7504 KB Output is correct
45 Correct 535 ms 7072 KB Output is correct
46 Correct 524 ms 7176 KB Output is correct
47 Correct 514 ms 7052 KB Output is correct
48 Correct 513 ms 7312 KB Output is correct
49 Correct 750 ms 110580 KB Output is correct
50 Correct 797 ms 110540 KB Output is correct
51 Correct 653 ms 7624 KB Output is correct
52 Correct 647 ms 7088 KB Output is correct
53 Correct 674 ms 90884 KB Output is correct
54 Correct 698 ms 111192 KB Output is correct
55 Correct 552 ms 90952 KB Output is correct
56 Correct 550 ms 116944 KB Output is correct
57 Correct 645 ms 7600 KB Output is correct
58 Correct 650 ms 7784 KB Output is correct
59 Correct 649 ms 7172 KB Output is correct
60 Correct 638 ms 7204 KB Output is correct
61 Correct 641 ms 110420 KB Output is correct
62 Correct 593 ms 91220 KB Output is correct
63 Correct 588 ms 109528 KB Output is correct
64 Correct 763 ms 110392 KB Output is correct
65 Correct 678 ms 90920 KB Output is correct
66 Correct 546 ms 108152 KB Output is correct
67 Correct 859 ms 110360 KB Output is correct
68 Correct 791 ms 91348 KB Output is correct
69 Correct 548 ms 108256 KB Output is correct
70 Correct 602 ms 110412 KB Output is correct
71 Correct 563 ms 91228 KB Output is correct
72 Correct 560 ms 114360 KB Output is correct
73 Correct 610 ms 110424 KB Output is correct
74 Correct 558 ms 91140 KB Output is correct
75 Correct 575 ms 117544 KB Output is correct
76 Correct 742 ms 110640 KB Output is correct
77 Correct 594 ms 110072 KB Output is correct
78 Correct 592 ms 110208 KB Output is correct
79 Correct 651 ms 7460 KB Output is correct
80 Correct 521 ms 7264 KB Output is correct
81 Correct 518 ms 7124 KB Output is correct
82 Correct 746 ms 110540 KB Output is correct
83 Correct 759 ms 133632 KB Output is correct
84 Correct 596 ms 109948 KB Output is correct
85 Correct 635 ms 146368 KB Output is correct
86 Correct 593 ms 110168 KB Output is correct
87 Correct 631 ms 132464 KB Output is correct
88 Correct 650 ms 7556 KB Output is correct
89 Correct 644 ms 7464 KB Output is correct
90 Correct 514 ms 7228 KB Output is correct
91 Correct 520 ms 7124 KB Output is correct
92 Correct 514 ms 7184 KB Output is correct
93 Correct 508 ms 7080 KB Output is correct
94 Correct 610 ms 74060 KB Output is correct
95 Correct 628 ms 91260 KB Output is correct
96 Correct 458 ms 73128 KB Output is correct
97 Correct 488 ms 92848 KB Output is correct
98 Correct 466 ms 73876 KB Output is correct
99 Correct 472 ms 90980 KB Output is correct
100 Correct 668 ms 7496 KB Output is correct
101 Correct 667 ms 7672 KB Output is correct
102 Correct 542 ms 7168 KB Output is correct
103 Correct 542 ms 7248 KB Output is correct
104 Correct 544 ms 7136 KB Output is correct
105 Correct 537 ms 7064 KB Output is correct
106 Correct 680 ms 90956 KB Output is correct
107 Correct 708 ms 120392 KB Output is correct
108 Correct 556 ms 90952 KB Output is correct
109 Correct 540 ms 105128 KB Output is correct
110 Correct 527 ms 91328 KB Output is correct
111 Correct 549 ms 105492 KB Output is correct
112 Correct 653 ms 7564 KB Output is correct
113 Correct 666 ms 7468 KB Output is correct
114 Correct 521 ms 7248 KB Output is correct
115 Correct 522 ms 7248 KB Output is correct
116 Correct 518 ms 7076 KB Output is correct
117 Correct 516 ms 7124 KB Output is correct
118 Correct 605 ms 110344 KB Output is correct
119 Correct 531 ms 90888 KB Output is correct
120 Correct 586 ms 118708 KB Output is correct
121 Correct 611 ms 110124 KB Output is correct
122 Correct 539 ms 90700 KB Output is correct
123 Correct 562 ms 116928 KB Output is correct
124 Correct 596 ms 110032 KB Output is correct
125 Correct 529 ms 91156 KB Output is correct
126 Correct 546 ms 115188 KB Output is correct