제출 #396465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
396465		pure_mem	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1397 ms	429764 KiB

bitaro

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 4e5 + 1, BS = 330;            
const ll INF = 1e18;

int n, m, q, dsu[N], used[N], cnt[N], dp[N];
vector< int > g[N];
vector< pair<int, int> > gg[N];
int ptr[N];

void prep(){
	cin >> n >> m >> q;
	for(int i = 1, x, y;i <= m;i++){
		cin >> x >> y;
		g[y].push_back(x);	
	}
	for(int i = 1;i <= n;i++){		
		for(int from: g[i])
			ptr[from] = 0;
		while(gg[i].size() <= BS + 1){
			int mx = -1;
			pair<int, int> need = MP(0, 0);
			for(int from: g[i]){		
				while(ptr[from] < gg[from].size() && used[gg[from][ptr[from]].Y] == i)
					ptr[from]++;
				if(ptr[from] < gg[from].size() && (mx == -1 || need.X < gg[from][ptr[from]].X))
					need = gg[from][ptr[from]], mx = from;
			}	
			need.X++;
			if(mx == -1)
				break;
			else
				gg[i].push_back(need), used[need.Y] = i, ptr[mx]++;
		}
		if(gg[i].size() <= BS + 1)
			gg[i].push_back(MP(0, i));
	}
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	prep();
	for(int pos, len, x, T = N + 1;q--;T++){
		cin >> pos >> len;
		for(int j = 1;j <= len;j++){
			cin >> x, used[x] = T;
		}
		if(len > 300){
			for(int i = 1;i <= pos;i++){
				dp[i] = 0, cnt[i] = 0;
				if(used[i] != T)
					cnt[i] = 1;
				for(int from: g[i]){
            		if(dp[from] + 1 > dp[i] && cnt[from])
            			dp[i] = dp[from] + 1, cnt[i] = cnt[from];
            		else if(dp[from] + 1 == dp[i] && cnt[from])
            			cnt[i]++; 
            	}	
			}
		} 
		else {
			dp[pos] = 0, cnt[pos] = 0;
			for(pair<int, int> tmp: gg[pos]){
				if(used[tmp.Y] == T)
					continue;
				if(tmp.X > dp[pos])
					dp[pos] = tmp.X, cnt[pos] = 1;
				else if(tmp.X == dp[pos])
					cnt[pos]++;	
			}	
		}
		cout << (cnt[pos] == 0 ? -1: dp[pos]) << "\n";
	}
}

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

bitaro.cpp: In function 'void prep()':
bitaro.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while(ptr[from] < gg[from].size() && used[gg[from][ptr[from]].Y] == i)
      |           ~~~~~~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:33: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]
   33 |     if(ptr[from] < gg[from].size() && (mx == -1 || need.X < gg[from][ptr[from]].X))
      |        ~~~~~~~~~~^~~~~~~~~~~~~~~~~

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