제출 #902358

#제출 시각아이디문제언어결과실행 시간메모리
902358yellowtoadBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2031 ms195280 KiB
#include <iostream> #include <vector> #include <queue> #include <math.h> #include <algorithm> #define f first #define s second using namespace std; const int LIM = sqrt(1e5); int n, m, test, hv[100010], dpp[100010]; vector<pair<int,int>> dp[100010]; vector<int> edge[100010], tnp; vector<pair<int,int>> tmp; priority_queue<pair<int,int>> pq; int main() { cin >> n >> m >> test; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; edge[v].push_back(u); } for (int i = 1; i <= n; i++) { int maxx = -1; tnp.push_back(i); for (int j = 0; j < edge[i].size(); j++) { for (int k = 0; k < dp[edge[i][j]].size(); k++) { hv[dp[edge[i][j]][k].s] = max(hv[dp[edge[i][j]][k].s],dp[edge[i][j]][k].f+1); tnp.push_back(dp[edge[i][j]][k].s); } } sort(tnp.begin(),tnp.end()); for (int j = 0; j < tnp.size(); j++) { if ((j == 0) || (tnp[j] != tnp[j-1])) { tmp.push_back({hv[tnp[j]],tnp[j]}); } } sort(tmp.begin(),tmp.end(),greater<pair<int,int>>()); for (int j = 0; j < min(LIM,(int)tmp.size()); j++) dp[i].push_back(tmp[j]); tmp.clear(); while (tnp.size()) { hv[tnp.back()] = 0; tnp.pop_back(); } } /*for (int i = 1; i <= n; i++) { for (int j = 0; j < dp[i].size(); j++) cout << dp[i][j].s << " "; cout << endl; }*/ while (test--) { int u, x; cin >> u >> m; for (int i = 1; i <= m; i++) { cin >> x; tnp.push_back(x); hv[x] = 1; } if (m <= LIM) { for (int i = 0; i < dp[u].size(); i++) { if (!hv[dp[u][i].s]) { cout << dp[u][i].f << endl; goto skip; } } cout << -1 << endl; skip:; } else { for (int i = 1; i <= u; i++) { if (hv[i]) dpp[i] = -1e9; for (int j = 0; j < edge[i].size(); j++) dpp[i] = max(dpp[i],dpp[edge[i][j]]+1); } if (dpp[u] < 0) cout << -1 << endl; else cout << dpp[u] << endl; } while (tnp.size()) { hv[tnp.back()] = 0; tnp.pop_back(); } } }

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int j = 0; j < edge[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~
bitaro.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for (int k = 0; k < dp[edge[i][j]].size(); k++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for (int j = 0; j < tnp.size(); j++) {
      |                   ~~^~~~~~~~~~~~
bitaro.cpp:25:7: warning: unused variable 'maxx' [-Wunused-variable]
   25 |   int maxx = -1;
      |       ^~~~
bitaro.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for (int i = 0; i < dp[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
bitaro.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int j = 0; j < edge[i].size(); j++) dpp[i] = max(dpp[i],dpp[edge[i][j]]+1);
      |                     ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...