제출 #383476

#제출 시각아이디문제언어결과실행 시간메모리
383476moratoBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2122 ms418020 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXS = 320; vector<int> adj[MAXN], rev[MAXN]; vector<pair<int, int>> caras[MAXN]; int in[MAXN], bosta[MAXN], best[MAXN]; pair<int, int> revIn[MAXN]; bool mark[MAXN], blocked[MAXN], valid[MAXN]; void merge(int a, int b) { vector<pair<int, int>> result; int j = 0; for (int i = 0; i < (int) caras[a].size(); i++) { for (; j < (int) caras[b].size() && caras[b][j].first + 1 > caras[a][i].first; j++) { result.push_back({caras[b][j].first + 1, caras[b][j].second}); } result.push_back(caras[a][i]); } for (; j < (int) caras[b].size(); j++) { result.push_back({caras[b][j].first + 1, caras[b][j].second}); } caras[a].clear(); for (int i = 0; i < (int) result.size() && (int) caras[a].size() < MAXS; i++) { if (!mark[result[i].second]) { caras[a].push_back(result[i]); mark[result[i].second] = true; } } for (auto x : caras[a]) { mark[x.second] = false; } } void solve(int t, int n) { vector<int> lista; for (int j = 1; j <= n; j++) { best[j] = -1; revIn[j].first = revIn[j].second; if (!revIn[j].first) lista.push_back(j); } valid[t] = true; best[t] = 0; for (int j = 0; j < (int) lista.size(); j++) { int cur = lista[j]; for (int nxt : rev[cur]) { revIn[nxt].first--; if (!revIn[nxt].first) lista.push_back(nxt); if (valid[cur]) { valid[nxt] = true; best[nxt] = max(best[nxt], best[cur] + 1); } } } } int main(){ int n, m, q; scanf("%d %d %d", &n, &m, &q); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); adj[a].push_back(b); rev[b].push_back(a); in[b]++; revIn[a].first++; } for (int i = 1; i <= n; i++) { revIn[i].second = revIn[i].first; } vector<int> lista; for (int i = 1; i <= n; i++) { caras[i].push_back({0, i}); if (!in[i]) lista.push_back(i); } for (int i = 0; i < (int) lista.size(); i++) { int cur = lista[i]; for (int nxt : adj[cur]) { in[nxt]--; if (!in[nxt]) lista.push_back(nxt); merge(nxt, cur); } } for (int i = 0; i < q; i++) { int t, y; scanf("%d %d", &t, &y); for (int j = 0; j < y; j++) { scanf("%d", &bosta[j]); blocked[bosta[j]] = true; } if (y > MAXS) { solve(t, n); int ans = -1; for (int j = 1; j <= t; j++) { valid[j] = false; if (!blocked[j]) ans = max(ans, best[j]); } printf("%d\n", ans); } else { int ans = -1; for (auto x : caras[t]) { if (!blocked[x.second]) { ans = x.first; break; } } printf("%d\n", ans); } for (int j = 0; j < y; j++) { blocked[bosta[j]] = false; } } return 0; }

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |   scanf("%d %d", &t, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:95:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |    scanf("%d", &bosta[j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...