oj.uz

Submission #406643

# Submission time Handle Problem Language Result Execution time Memory
406643 2021-05-17T23:16:15 Z azberjibiou Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 949 ms 289336 KB 
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=100010;
const int mxM=350;
const int mxK=350;
const ll MOD=1000000007;
const ll INF=100000000000001;
int N, M, Q;
vector <int> v[mxN], rv[mxN];
int deg[mxN];
vector <pii> num[mxN];
vector <pii> tmpv1, tmpv2, tmpv3;
int Chk[mxN];
int idx=1;
int dp[mxN];
int main()
{
    gibon
    cin >> N >> M >> Q;
    for(int i=1;i<=M;i++)
    {
        int a, b;
        cin >> a >> b;
        v[b].push_back(a);
    }
    for(int now=1;now<=N;now++)
    {
        tmpv3.clear();
        tmpv3.push_back({now, 0});
        for(int nxt : v[now])
        {
            tmpv1.clear();
            swap(tmpv1, tmpv3);
            tmpv2.clear();  tmpv2.resize(num[nxt].size());  for(int i=0;i<num[nxt].size();i++)  tmpv2[i]=num[nxt][i];
            for(int i=0;i<tmpv2.size();i++) tmpv2[i].sec++;
            int cur1=0, cur2=0;
            while(cur1!=tmpv1.size() && cur2!=tmpv2.size() && tmpv3.size()<=mxK)
            {
                if(tmpv1[cur1].sec>tmpv2[cur2].sec)
                {
                    if(Chk[tmpv1[cur1].fir]==idx)   cur1++;
                    else
                    {
                        tmpv3.push_back(tmpv1[cur1]);
                        Chk[tmpv1[cur1++].fir]=idx;
                    }
                }
                else
                {
                    if(Chk[tmpv2[cur2].fir]==idx)   cur2++;
                    else
                    {
                        tmpv3.push_back(tmpv2[cur2]);
                        Chk[tmpv2[cur2++].fir]=idx;
                    }
                }
            }
            while(tmpv3.size()<=mxK && cur1!=tmpv1.size())
            {
                if(Chk[tmpv1[cur1].fir]==idx)   cur1++;
                else    tmpv3.push_back(tmpv1[cur1++]);
            }
            while(tmpv3.size()<=mxK && cur2!=tmpv2.size())
            {
                if(Chk[tmpv2[cur2].fir]==idx)   cur2++;
                else    tmpv3.push_back(tmpv2[cur2++]);
            }
            idx++;
        }
        num[now].resize(tmpv3.size());  for(int i=0;i<tmpv3.size();i++) num[now][i]=tmpv3[i];
    }
    while(Q--)
    {
        int ans=-1;
        int T, Y;
        cin >> T >> Y;
        for(int i=0;i<Y;i++)
        {
            int a;  cin >> a;
            Chk[a]=idx;
        }
        if(Y<mxK)
        {
            for(pii nxt : num[T])   if(Chk[nxt.fir]!=idx)
            {
                ans=nxt.sec;
                break;
            }
            cout << ans << '\n';
        }
        else
        {
            for(int i=1;i<=T;i++)   dp[i]=-1;
            for(int now=1;now<=T;now++)
            {
                if(Chk[now]!=idx)   dp[now]=0;
                for(int nxt : v[now])   if(dp[nxt]!=-1)
                {
                    dp[now]=max(dp[now], dp[nxt]+1);
                }
            }
            cout << dp[T] << '\n';
        }
        idx++;
    }
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:45:74: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             tmpv2.clear();  tmpv2.resize(num[nxt].size());  for(int i=0;i<num[nxt].size();i++)  tmpv2[i]=num[nxt][i];
      |                                                                         ~^~~~~~~~~~~~~~~~
bitaro.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int i=0;i<tmpv2.size();i++) tmpv2[i].sec++;
      |                         ~^~~~~~~~~~~~~
bitaro.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             while(cur1!=tmpv1.size() && cur2!=tmpv2.size() && tmpv3.size()<=mxK)
      |                   ~~~~^~~~~~~~~~~~~~
bitaro.cpp:48:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             while(cur1!=tmpv1.size() && cur2!=tmpv2.size() && tmpv3.size()<=mxK)
      |                                         ~~~~^~~~~~~~~~~~~~
bitaro.cpp:69:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             while(tmpv3.size()<=mxK && cur1!=tmpv1.size())
      |                                        ~~~~^~~~~~~~~~~~~~
bitaro.cpp:74:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             while(tmpv3.size()<=mxK && cur2!=tmpv2.size())
      |                                        ~~~~^~~~~~~~~~~~~~
bitaro.cpp:81:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         num[now].resize(tmpv3.size());  for(int i=0;i<tmpv3.size();i++) num[now][i]=tmpv3[i];
      |                                                     ~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7368 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 7 ms 7628 KB Output is correct
6 Correct 7 ms 7628 KB Output is correct
7 Correct 7 ms 7624 KB Output is correct
8 Correct 12 ms 10080 KB Output is correct
9 Correct 12 ms 10188 KB Output is correct
10 Correct 13 ms 10188 KB Output is correct
11 Correct 12 ms 9368 KB Output is correct
12 Correct 8 ms 8276 KB Output is correct
13 Correct 12 ms 9324 KB Output is correct
14 Correct 10 ms 8728 KB Output is correct
15 Correct 8 ms 8012 KB Output is correct
16 Correct 10 ms 8660 KB Output is correct
17 Correct 10 ms 8908 KB Output is correct
18 Correct 8 ms 8140 KB Output is correct
19 Correct 10 ms 8908 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7368 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 7 ms 7628 KB Output is correct
6 Correct 7 ms 7628 KB Output is correct
7 Correct 7 ms 7624 KB Output is correct
8 Correct 12 ms 10080 KB Output is correct
9 Correct 12 ms 10188 KB Output is correct
10 Correct 13 ms 10188 KB Output is correct
11 Correct 12 ms 9368 KB Output is correct
12 Correct 8 ms 8276 KB Output is correct
13 Correct 12 ms 9324 KB Output is correct
14 Correct 10 ms 8728 KB Output is correct
15 Correct 8 ms 8012 KB Output is correct
16 Correct 10 ms 8660 KB Output is correct
17 Correct 10 ms 8908 KB Output is correct
18 Correct 8 ms 8140 KB Output is correct
19 Correct 10 ms 8908 KB Output is correct
20 Correct 554 ms 12472 KB Output is correct
21 Correct 463 ms 12600 KB Output is correct
22 Correct 556 ms 12560 KB Output is correct
23 Correct 584 ms 12612 KB Output is correct
24 Correct 662 ms 177688 KB Output is correct
25 Correct 687 ms 185224 KB Output is correct
26 Correct 685 ms 185028 KB Output is correct
27 Correct 871 ms 289188 KB Output is correct
28 Correct 879 ms 288976 KB Output is correct
29 Correct 879 ms 288720 KB Output is correct
30 Correct 892 ms 287672 KB Output is correct
31 Correct 883 ms 277696 KB Output is correct
32 Correct 892 ms 287212 KB Output is correct
33 Correct 587 ms 179496 KB Output is correct
34 Correct 545 ms 148220 KB Output is correct
35 Correct 583 ms 178456 KB Output is correct
36 Correct 700 ms 233564 KB Output is correct
37 Correct 670 ms 211664 KB Output is correct
38 Correct 709 ms 234180 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7368 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 7 ms 7628 KB Output is correct
6 Correct 7 ms 7628 KB Output is correct
7 Correct 7 ms 7624 KB Output is correct
8 Correct 12 ms 10080 KB Output is correct
9 Correct 12 ms 10188 KB Output is correct
10 Correct 13 ms 10188 KB Output is correct
11 Correct 12 ms 9368 KB Output is correct
12 Correct 8 ms 8276 KB Output is correct
13 Correct 12 ms 9324 KB Output is correct
14 Correct 10 ms 8728 KB Output is correct
15 Correct 8 ms 8012 KB Output is correct
16 Correct 10 ms 8660 KB Output is correct
17 Correct 10 ms 8908 KB Output is correct
18 Correct 8 ms 8140 KB Output is correct
19 Correct 10 ms 8908 KB Output is correct
20 Correct 554 ms 12472 KB Output is correct
21 Correct 463 ms 12600 KB Output is correct
22 Correct 556 ms 12560 KB Output is correct
23 Correct 584 ms 12612 KB Output is correct
24 Correct 662 ms 177688 KB Output is correct
25 Correct 687 ms 185224 KB Output is correct
26 Correct 685 ms 185028 KB Output is correct
27 Correct 871 ms 289188 KB Output is correct
28 Correct 879 ms 288976 KB Output is correct
29 Correct 879 ms 288720 KB Output is correct
30 Correct 892 ms 287672 KB Output is correct
31 Correct 883 ms 277696 KB Output is correct
32 Correct 892 ms 287212 KB Output is correct
33 Correct 587 ms 179496 KB Output is correct
34 Correct 545 ms 148220 KB Output is correct
35 Correct 583 ms 178456 KB Output is correct
36 Correct 700 ms 233564 KB Output is correct
37 Correct 670 ms 211664 KB Output is correct
38 Correct 709 ms 234180 KB Output is correct
39 Correct 711 ms 180240 KB Output is correct
40 Correct 672 ms 180468 KB Output is correct
41 Correct 688 ms 182068 KB Output is correct
42 Correct 753 ms 181656 KB Output is correct
43 Correct 703 ms 180996 KB Output is correct
44 Correct 586 ms 12868 KB Output is correct
45 Correct 567 ms 12096 KB Output is correct
46 Correct 557 ms 11900 KB Output is correct
47 Correct 587 ms 11844 KB Output is correct
48 Correct 544 ms 12008 KB Output is correct
49 Correct 932 ms 289336 KB Output is correct
50 Correct 886 ms 287976 KB Output is correct
51 Correct 497 ms 13176 KB Output is correct
52 Correct 476 ms 12300 KB Output is correct
53 Correct 787 ms 233884 KB Output is correct
54 Correct 710 ms 213328 KB Output is correct
55 Correct 697 ms 233156 KB Output is correct
56 Correct 665 ms 212036 KB Output is correct
57 Correct 572 ms 12612 KB Output is correct
58 Correct 595 ms 12616 KB Output is correct
59 Correct 538 ms 12212 KB Output is correct
60 Correct 559 ms 12228 KB Output is correct
61 Correct 949 ms 287672 KB Output is correct
62 Correct 767 ms 233692 KB Output is correct
63 Correct 742 ms 211264 KB Output is correct
64 Correct 928 ms 287520 KB Output is correct
65 Correct 735 ms 232600 KB Output is correct
66 Correct 719 ms 212316 KB Output is correct
67 Correct 882 ms 287272 KB Output is correct
68 Correct 710 ms 233176 KB Output is correct
69 Correct 660 ms 209296 KB Output is correct
70 Correct 887 ms 287580 KB Output is correct
71 Correct 715 ms 233420 KB Output is correct
72 Correct 682 ms 211904 KB Output is correct
73 Correct 909 ms 287552 KB Output is correct
74 Correct 727 ms 233540 KB Output is correct
75 Correct 699 ms 212076 KB Output is correct
76 Correct 930 ms 288040 KB Output is correct
77 Correct 877 ms 287552 KB Output is correct
78 Correct 886 ms 287920 KB Output is correct
79 Correct 502 ms 12356 KB Output is correct
80 Correct 475 ms 11984 KB Output is correct
81 Correct 466 ms 12108 KB Output is correct
82 Correct 926 ms 287412 KB Output is correct
83 Correct 915 ms 277200 KB Output is correct
84 Correct 889 ms 286572 KB Output is correct
85 Correct 871 ms 276300 KB Output is correct
86 Correct 884 ms 286932 KB Output is correct
87 Correct 880 ms 277316 KB Output is correct
88 Correct 582 ms 12312 KB Output is correct
89 Correct 594 ms 12424 KB Output is correct
90 Correct 551 ms 11880 KB Output is correct
91 Correct 568 ms 12012 KB Output is correct
92 Correct 541 ms 11920 KB Output is correct
93 Correct 550 ms 11908 KB Output is correct
94 Correct 624 ms 179144 KB Output is correct
95 Correct 577 ms 146732 KB Output is correct
96 Correct 588 ms 178000 KB Output is correct
97 Correct 535 ms 149172 KB Output is correct
98 Correct 602 ms 179008 KB Output is correct
99 Correct 547 ms 148968 KB Output is correct
100 Correct 639 ms 12152 KB Output is correct
101 Correct 626 ms 12056 KB Output is correct
102 Correct 608 ms 11824 KB Output is correct
103 Correct 615 ms 11720 KB Output is correct
104 Correct 623 ms 11844 KB Output is correct
105 Correct 609 ms 11776 KB Output is correct
106 Correct 734 ms 232388 KB Output is correct
107 Correct 728 ms 211716 KB Output is correct
108 Correct 710 ms 233596 KB Output is correct
109 Correct 658 ms 210884 KB Output is correct
110 Correct 716 ms 233764 KB Output is correct
111 Correct 672 ms 212092 KB Output is correct
112 Correct 574 ms 12348 KB Output is correct
113 Correct 605 ms 12240 KB Output is correct
114 Correct 539 ms 11976 KB Output is correct
115 Correct 563 ms 11804 KB Output is correct
116 Correct 537 ms 11920 KB Output is correct
117 Correct 565 ms 11844 KB Output is correct
118 Correct 873 ms 286992 KB Output is correct
119 Correct 696 ms 233360 KB Output is correct
120 Correct 669 ms 210884 KB Output is correct
121 Correct 880 ms 287068 KB Output is correct
122 Correct 710 ms 232364 KB Output is correct
123 Correct 662 ms 211064 KB Output is correct
124 Correct 878 ms 286944 KB Output is correct
125 Correct 691 ms 233668 KB Output is correct
126 Correct 648 ms 210392 KB Output is correct