제출 #1107665

#제출 시각아이디문제언어결과실행 시간메모리
1107665bLICBitaro’s Party (JOI18_bitaro)C++17
0 / 100
2073 ms7760 KiB
/** * Author: Anil Byar **/ #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; // template<class T> // using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)(x).size() #define uniq(v) v.erase(unique(all(v)), v.end()) #define ft first #define sd second #define pb push_back #define eb emplace_back // Source: https://codeforces.com/blog/entry/68809 // { start void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif // } end typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef vector<vl> vvl; #define dbg if(0) const ll MOD = 1e9+7; const ll MOD9 = 998244353; const ll INFLL = 1e18+5; const int INF = 1e9; void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;} ll power(ll x, ll y, ll mod){if (y==0) return 1;ll ret = power(x, y/2, mod);ret *= ret;ret%=mod;if (y&1) ret *= x;return ret%mod;} ll modinv(ll x, ll mod = MOD) {return power(x, mod-2, mod);} template<class T> bool chmin(T& a, T b){return (a>b?a=b,1:0);} template<class T> bool chmax(T& a, T b){return (a<b?a=b,1:0);} template<class T> istream& operator>>(istream&in, vector<T>&v){ for (T& x:v) in>>x; return in; } template<class T> ostream& operator<<(ostream&out, vector<T>&v){ for (T& x:v) out<<x<<' '; cout<<'\n'; return out; } // use ?: with brackets (?:) // check for overflow // think about dp // Read the statement carefully const int N = 1e5+5; const int B = 88; vi adj[N]; vii s[N]; int ans[N]; bool removed[N], vis[N]; void calcDfs(int node, int par) { if (vis[node]) return; if (!removed[node]) ans[node] = 0; else ans[node] = -INF; for (int x:adj[node]) if (x!=par) { calcDfs(x, node); chmax(ans[node], ans[x] + 1); } } void solve(){ int n, m, q;cin>>n>>m>>q; for (int i = 0;i<m;i++) { int a, b;cin>>a>>b; adj[b].push_back(a); } memset(vis, false, sizeof(vis)); for (int node = 1;node<=n;node++) { s[node].push_back({0, node}); for (int x:adj[node]) { for (auto y:s[x]) { s[node].push_back({y.first + 1, y.second}); } } sort(rall(s[node])); while (sz(s[node])>B) s[node].pop_back(); } while (q--) { int t, y;cin>>t>>y; vi a(y); for (int i = 0;i<y;i++) { cin>>a[i]; removed[a[i]] = true; } if (y<B) { bool found = false; for (auto yy:s[t]) { if (!removed[yy.second]) { cout<<yy.first; found = true; break; } } if (!found) cout<<-1; } else { for (int i = 1;i<=n;i++) vis[i] = false; calcDfs(t, -1); cout<<max(-1, ans[t]); } for (int i = 0;i<y;i++) { removed[a[i]] = false; } cout<<'\n'; } debug(B); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1, i = 1; // cin>>t; while(t--){ cerr<<"Test Case: "<<i++<<'\n'; solve(); cout<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...