제출 #62724

#제출 시각아이디문제언어결과실행 시간메모리
62724kingpig9Bitaro’s Party (JOI18_bitaro)C++11
0 / 100
13 ms8124 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5 + 10; const int SQRT = 320; #define debug(...) fprintf(stderr, __VA_ARGS__) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) int N, M, Q; vector<int> adj[MAXN], radj[MAXN]; vector<pii> far[MAXN]; //farthest SQRT vertices: pair(dist, vertex) pii tmp[2 * SQRT]; bool vis[MAXN]; void merge (vector<pii> &v, const vector<pii> &w) { int sz = merge(all(v), all(w), tmp, greater<pii> ()) - tmp; v.clear(); for (int i = 0; i < sz && v.size() < SQRT; i++) { if (!vis[tmp[i].se]) { v.push_back(tmp[i]); vis[tmp[i].se] = true; } } for (int i = 0; i < sz; i++) { vis[tmp[i].se] = false; } } bool busy[MAXN]; int dp[MAXN]; int main() { scanf("%d %d %d", &N, &M, &Q); for (int i = 1; i <= M; i++) { int x, y; scanf("%d %d", &x, &y); adj[x].push_back(y); radj[y].push_back(x); } for (int i = 1; i <= N; i++) { far[i].push_back({0, i}); for (int j : radj[i]) { vector<pii> vtmp = far[j]; for (pii &p : vtmp) { p.fi++; } merge(far[i], vtmp); } } //if size >= SQRT then brute force for (int qi = 1; qi <= Q; qi++) { int x, sz; scanf("%d %d", &x, &sz); vector<int> vbusy(sz); for (int &c : vbusy) { scanf("%d", &c); busy[c] = true; } int ans = -1; if (sz < SQRT) { //the farthest away -- one of them will not be for (pii p : far[x]) { if (!busy[p.se]) { ans = p.fi; break; } } } else { //brute force for (int i = x; i >= 1; i--) { dp[i] = 0; } for (int i = x; i >= 1; i--) { for (int j : radj[i]) { dp[j] = max(dp[j], dp[i] + 1); } if (!busy[i]) { ans = max(ans, dp[i]); } } } printf("%d\n", ans); for (int c : vbusy) { busy[c] = false; } } }

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &sz);
   ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:68:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &c);
    ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...