Submission #1266044

#TimeUsernameProblemLanguageResultExecution timeMemory
1266044icebearBitaro’s Party (JOI18_bitaro)C++20
0 / 100
2 ms4932 KiB
// ~~ icebear ~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class T> bool minimize(T &a, const T &b) { if (a > b) return a = b, true; return false; } template<class T> bool maximize(T &a, const T &b) { if (a < b) return a = b, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "icebear" const int MOD = 1e9 + 7; const int inf = 1e9 + 27092008; const ll INF = 1e18 + 27092008; const int N = 2e5 + 5; const int S = 1001; int n, m, q; ii dist[S][N], tmp[S]; vector<int> G[N]; int f[N]; void mergeDist(int u, int v) { int i = 0, j = 0, cur = 0; while(cur < S) { if (i < S && f[dist[i][u].se] > 0) { i++; continue; } if (j < S && f[dist[j][v].se] > 0) { j++; continue; } if (i < S && dist[i][u].se > 0 && (j == S || dist[i][u].fi > dist[j][v].fi + 1 || dist[j][v].se == 0)) { tmp[cur++] = dist[i][u]; f[dist[i][u].se] = 1; i++; } else if (j < S && dist[j][v].se > 0) { tmp[cur++] = mp(dist[j][v].fi + 1, dist[j][v].se); f[dist[j][v].se] = 1; j++; } else break; } REP(i, cur) dist[i][u] = tmp[i], f[tmp[i].se] = 0; } void prepareDist() { FOR(i, 1, n) { dist[0][i] = mp(0, i); for(int v : G[i]) mergeDist(i, v); } } void init(void) { cin >> n >> m >> q; FOR(i, 1, m) { int u, v; cin >> u >> v; if (u < v) swap(u, v); G[u].pb(v); } } void process(void) { vector<bool> inQuery(n + 5, false); prepareDist(); while(q--) { int T, k; cin >> T >> k; vector<int> nodes(k); for(int &i : nodes) cin >> i, inQuery[i] = true; bool haveAns = false; if (k < S) { REP(i, S) if (!inQuery[dist[i][T].se]) { cout << dist[i][T].fi << '\n'; haveAns = true; break; } } else { FOR(i, 1, n) f[i] = 0; FOR(i, 1, T) { for(int v : G[i]) if (!inQuery[v] || (inQuery[v] && f[v] > 0)) maximize(f[i], f[v] + 1); } if (f[T] > 0) { cout << f[T] << '\n'; haveAns = true; } } if (!haveAns) cout << -1 << '\n'; for(int &i : nodes) inQuery[i] = false; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int tc = 1; // cin >> tc; while(tc--) { init(); process(); } return 0; }

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...