Submission #768585

#	Time	Username	Problem	Language	Result	Execution time	Memory
768585		AdamGS	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	762 ms	89164 KiB

bitaro

            #include<bits/stdc++.h>
            using namespace std;
            #define rep(a, b) for(int a = 0; a < (b); ++a)
            #define st first
            #define nd second
            #define pb push_back
            #define all(a) a.begin(), a.end()
            const int LIM=1e5+7, K=100, INF=1e9+7;
            vector<int>V[LIM];
            vector<pair<int,int>>P[LIM];
            int odw[LIM], kiedy[LIM], czy[LIM], najd[LIM], akt, akt2;
            void lacz(int a, int b) {
            	++akt;
            	vector<pair<int,int>>tmp;
            	int la=0, lb=0;
            	while(tmp.size()<K && (la<P[a].size() || lb<P[b].size())) {
            		if(lb==P[b].size() || la<P[a].size() && P[a][la].nd>=P[b][lb].nd+1) {
            			if(kiedy[P[a][la].st]<akt) {
            				kiedy[P[a][la].st]=akt;
            				tmp.pb(P[a][la]);
            			}
            			++la;
            		} else {
            			if(kiedy[P[b][lb].st]<akt) {
            				kiedy[P[b][lb].st]=akt;
            				tmp.pb({P[b][lb].st, P[b][lb].nd+1});
            			}
            			++lb;
            		}
            	}
            	P[a]=tmp;
            }
            void DFS(int x) {
            	odw[x]=1;
            	P[x].pb({x, 0});
            	for(auto i : V[x]) {
            		if(!odw[i]) DFS(i);
            		lacz(x, i);
            	}
            }
            int main() {
            	ios_base::sync_with_stdio(0); cin.tie(0);
            	int n, m, q;
            	cin >> n >> m >> q;
            	while(m--) {
            		int a, b;
            		cin >> a >> b; --a; --b;
            		V[b].pb(a);
            	}
            	rep(i, n) if(!odw[i]) DFS(i);
            	while(q--) {
            		int x, y;
            		cin >> x >> y; --x;
            		++akt2;
            		rep(i, y) {
            			int a;
            			cin >> a; --a;
            			czy[a]=akt2;
            		}
            		if(y<K) {
            			int ans=-1;
            			for(auto i : P[x]) if(czy[i.st]<akt2) ans=max(ans, i.nd);
            			cout << ans << '\n';
            			continue;
            		}
                  	rep(i, n) {
                      if(czy[i]) najd[i]=-INF;
                      else najd[i]=0;
                      for(auto j : V[i]) najd[i]=max(najd[i], najd[j]+1);
                    }
            		cout << max(najd[x], -1) << '\n';
            	}
            }

Compilation message (stderr)

bitaro.cpp: In function 'void lacz(int, int)':
bitaro.cpp:16:39: 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(tmp.size()<K && (la<P[a].size() || lb<P[b].size())) {
      |                                     ~~^~~~~~~~~~~~
bitaro.cpp:16:57: 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(tmp.size()<K && (la<P[a].size() || lb<P[b].size())) {
      |                                                       ~~^~~~~~~~~~~~
bitaro.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |               if(lb==P[b].size() || la<P[a].size() && P[a][la].nd>=P[b][lb].nd+1) {
      |                  ~~^~~~~~~~~~~~~
bitaro.cpp:17:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |               if(lb==P[b].size() || la<P[a].size() && P[a][la].nd>=P[b][lb].nd+1) {
      |                                     ~~^~~~~~~~~~~~
bitaro.cpp:17:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   17 |               if(lb==P[b].size() || la<P[a].size() && P[a][la].nd>=P[b][lb].nd+1) {
      |                                     ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86