oj.uz

Submission #111087

# Submission time Handle Problem Language Result Execution time Memory
111087 2019-05-13T15:41:30 Z igzi Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 1561 ms 145140 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-2 && 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 between signed and unsigned integer expressions [-Wsign-compare]
 while(i<a.size() && j<b.size()){
       ~^~~~~~~~~
bitaro.cpp:16:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<a.size() && j<b.size()){
                     ~^~~~~~~~~
bitaro.cpp:20:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<a.size()){
       ~^~~~~~~~~
bitaro.cpp:23:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(j<b.size()){
       ~^~~~~~~~~
bitaro.cpp:27:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<v.size();i++){
         ~^~~~~~~~~
bitaro.cpp:30:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<u.size();i++) mar[u[i].second]=false;
         ~^~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<adj[i].size();j++){
                 ~^~~~~~~~~~~~~~
bitaro.cpp:59:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<d[t].size();i++){
                 ~^~~~~~~~~~~~
bitaro.cpp:70:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0;j<adj[i].size();j++){
                         ~^~~~~~~~~~~~~~
bitaro.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         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 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 12 ms 5504 KB Output is correct
6 Correct 12 ms 5504 KB Output is correct
7 Correct 12 ms 5504 KB Output is correct
8 Correct 15 ms 6144 KB Output is correct
9 Correct 16 ms 6144 KB Output is correct
10 Correct 14 ms 6016 KB Output is correct
11 Correct 15 ms 6016 KB Output is correct
12 Correct 12 ms 5888 KB Output is correct
13 Correct 14 ms 6016 KB Output is correct
14 Correct 13 ms 5760 KB Output is correct
15 Correct 11 ms 5504 KB Output is correct
16 Correct 12 ms 5760 KB Output is correct
17 Correct 12 ms 5760 KB Output is correct
18 Correct 13 ms 5636 KB Output is correct
19 Correct 13 ms 5888 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 12 ms 5504 KB Output is correct
6 Correct 12 ms 5504 KB Output is correct
7 Correct 12 ms 5504 KB Output is correct
8 Correct 15 ms 6144 KB Output is correct
9 Correct 16 ms 6144 KB Output is correct
10 Correct 14 ms 6016 KB Output is correct
11 Correct 15 ms 6016 KB Output is correct
12 Correct 12 ms 5888 KB Output is correct
13 Correct 14 ms 6016 KB Output is correct
14 Correct 13 ms 5760 KB Output is correct
15 Correct 11 ms 5504 KB Output is correct
16 Correct 12 ms 5760 KB Output is correct
17 Correct 12 ms 5760 KB Output is correct
18 Correct 13 ms 5636 KB Output is correct
19 Correct 13 ms 5888 KB Output is correct
20 Correct 753 ms 7424 KB Output is correct
21 Correct 666 ms 7288 KB Output is correct
22 Correct 702 ms 7208 KB Output is correct
23 Correct 752 ms 7288 KB Output is correct
24 Correct 1277 ms 105228 KB Output is correct
25 Correct 1155 ms 98012 KB Output is correct
26 Correct 1249 ms 97576 KB Output is correct
27 Correct 1088 ms 110712 KB Output is correct
28 Correct 931 ms 110564 KB Output is correct
29 Correct 957 ms 110836 KB Output is correct
30 Correct 1022 ms 110580 KB Output is correct
31 Correct 1236 ms 130860 KB Output is correct
32 Correct 1080 ms 110516 KB Output is correct
33 Correct 920 ms 73592 KB Output is correct
34 Correct 996 ms 86664 KB Output is correct
35 Correct 921 ms 73280 KB Output is correct
36 Correct 824 ms 91144 KB Output is correct
37 Correct 1180 ms 109160 KB Output is correct
38 Correct 851 ms 91504 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 12 ms 5504 KB Output is correct
6 Correct 12 ms 5504 KB Output is correct
7 Correct 12 ms 5504 KB Output is correct
8 Correct 15 ms 6144 KB Output is correct
9 Correct 16 ms 6144 KB Output is correct
10 Correct 14 ms 6016 KB Output is correct
11 Correct 15 ms 6016 KB Output is correct
12 Correct 12 ms 5888 KB Output is correct
13 Correct 14 ms 6016 KB Output is correct
14 Correct 13 ms 5760 KB Output is correct
15 Correct 11 ms 5504 KB Output is correct
16 Correct 12 ms 5760 KB Output is correct
17 Correct 12 ms 5760 KB Output is correct
18 Correct 13 ms 5636 KB Output is correct
19 Correct 13 ms 5888 KB Output is correct
20 Correct 753 ms 7424 KB Output is correct
21 Correct 666 ms 7288 KB Output is correct
22 Correct 702 ms 7208 KB Output is correct
23 Correct 752 ms 7288 KB Output is correct
24 Correct 1277 ms 105228 KB Output is correct
25 Correct 1155 ms 98012 KB Output is correct
26 Correct 1249 ms 97576 KB Output is correct
27 Correct 1088 ms 110712 KB Output is correct
28 Correct 931 ms 110564 KB Output is correct
29 Correct 957 ms 110836 KB Output is correct
30 Correct 1022 ms 110580 KB Output is correct
31 Correct 1236 ms 130860 KB Output is correct
32 Correct 1080 ms 110516 KB Output is correct
33 Correct 920 ms 73592 KB Output is correct
34 Correct 996 ms 86664 KB Output is correct
35 Correct 921 ms 73280 KB Output is correct
36 Correct 824 ms 91144 KB Output is correct
37 Correct 1180 ms 109160 KB Output is correct
38 Correct 851 ms 91504 KB Output is correct
39 Correct 1522 ms 105836 KB Output is correct
40 Correct 1272 ms 98708 KB Output is correct
41 Correct 1260 ms 102524 KB Output is correct
42 Correct 1328 ms 103180 KB Output is correct
43 Correct 1255 ms 107144 KB Output is correct
44 Correct 903 ms 10064 KB Output is correct
45 Correct 815 ms 9124 KB Output is correct
46 Correct 775 ms 9056 KB Output is correct
47 Correct 804 ms 8916 KB Output is correct
48 Correct 814 ms 8696 KB Output is correct
49 Correct 1309 ms 114152 KB Output is correct
50 Correct 1561 ms 113260 KB Output is correct
51 Correct 892 ms 9940 KB Output is correct
52 Correct 880 ms 9048 KB Output is correct
53 Correct 1092 ms 94364 KB Output is correct
54 Correct 1424 ms 111224 KB Output is correct
55 Correct 1046 ms 93732 KB Output is correct
56 Correct 1256 ms 117132 KB Output is correct
57 Correct 788 ms 10028 KB Output is correct
58 Correct 846 ms 10220 KB Output is correct
59 Correct 926 ms 9140 KB Output is correct
60 Correct 1043 ms 9184 KB Output is correct
61 Correct 1000 ms 113352 KB Output is correct
62 Correct 901 ms 94072 KB Output is correct
63 Correct 1249 ms 109868 KB Output is correct
64 Correct 1146 ms 113400 KB Output is correct
65 Correct 1000 ms 93804 KB Output is correct
66 Correct 1119 ms 108168 KB Output is correct
67 Correct 1458 ms 113400 KB Output is correct
68 Correct 1103 ms 94108 KB Output is correct
69 Correct 1158 ms 108756 KB Output is correct
70 Correct 806 ms 113400 KB Output is correct
71 Correct 817 ms 94072 KB Output is correct
72 Correct 1104 ms 114328 KB Output is correct
73 Correct 1008 ms 113272 KB Output is correct
74 Correct 981 ms 94224 KB Output is correct
75 Correct 1270 ms 117476 KB Output is correct
76 Correct 1313 ms 114436 KB Output is correct
77 Correct 1095 ms 113144 KB Output is correct
78 Correct 895 ms 113308 KB Output is correct
79 Correct 850 ms 10188 KB Output is correct
80 Correct 775 ms 9208 KB Output is correct
81 Correct 753 ms 8900 KB Output is correct
82 Correct 1306 ms 114424 KB Output is correct
83 Correct 1263 ms 134792 KB Output is correct
84 Correct 888 ms 113120 KB Output is correct
85 Correct 1062 ms 145140 KB Output is correct
86 Correct 973 ms 113272 KB Output is correct
87 Correct 1125 ms 132172 KB Output is correct
88 Correct 956 ms 10044 KB Output is correct
89 Correct 912 ms 9988 KB Output is correct
90 Correct 683 ms 9208 KB Output is correct
91 Correct 636 ms 9128 KB Output is correct
92 Correct 671 ms 8648 KB Output is correct
93 Correct 740 ms 8824 KB Output is correct
94 Correct 1183 ms 77512 KB Output is correct
95 Correct 1201 ms 92868 KB Output is correct
96 Correct 783 ms 76080 KB Output is correct
97 Correct 930 ms 93424 KB Output is correct
98 Correct 841 ms 76536 KB Output is correct
99 Correct 942 ms 91920 KB Output is correct
100 Correct 925 ms 10028 KB Output is correct
101 Correct 1027 ms 10044 KB Output is correct
102 Correct 687 ms 9072 KB Output is correct
103 Correct 799 ms 9116 KB Output is correct
104 Correct 726 ms 8804 KB Output is correct
105 Correct 803 ms 8812 KB Output is correct
106 Correct 1108 ms 94732 KB Output is correct
107 Correct 1357 ms 120236 KB Output is correct
108 Correct 993 ms 93932 KB Output is correct
109 Correct 1350 ms 106100 KB Output is correct
110 Correct 978 ms 94196 KB Output is correct
111 Correct 1341 ms 105748 KB Output is correct
112 Correct 880 ms 9976 KB Output is correct
113 Correct 841 ms 10024 KB Output is correct
114 Correct 724 ms 9140 KB Output is correct
115 Correct 754 ms 9300 KB Output is correct
116 Correct 772 ms 8824 KB Output is correct
117 Correct 755 ms 8824 KB Output is correct
118 Correct 1004 ms 112904 KB Output is correct
119 Correct 913 ms 93944 KB Output is correct
120 Correct 1136 ms 117984 KB Output is correct
121 Correct 1048 ms 113092 KB Output is correct
122 Correct 921 ms 93548 KB Output is correct
123 Correct 1155 ms 116272 KB Output is correct
124 Correct 1073 ms 112772 KB Output is correct
125 Correct 862 ms 93984 KB Output is correct
126 Correct 1234 ms 115164 KB Output is correct