제출 #768579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
768579		AdamGS	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1199 ms	173620 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()<200 && (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);
    	}
    }
    void DFS2(int x) {
    	odw[x]=1;
    	najd[x]=0;
    	if(czy[x]==akt2) najd[x]=-INF;
    	for(auto i : V[x]) {
    		if(!odw[i]) DFS2(i);
    		najd[x]=max(najd[x], najd[i]+1);
    	}
    }
    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) odw[i]=0;
    		DFS2(x);
    		cout << max(najd[x], -1) << '\n';
    	}
    }

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'void lacz(int, int)':
bitaro.cpp:16:33: 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()<200 && (la<P[a].size() || lb<P[b].size())) {
      |                               ~~^~~~~~~~~~~~
bitaro.cpp:16:51: 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()<200 && (la<P[a].size() || lb<P[b].size())) {
      |                                                 ~~^~~~~~~~~~~~
bitaro.cpp:17:12: 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:31: 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:44: 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: 86 / 86