제출 #718195

#제출 시각아이디문제언어결과실행 시간메모리
718195bLICRegions (IOI09_regions)C++17
3 / 100
3023 ms11620 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 ft first #define sd second #define pb push_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> 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 const int maxN = 1e5+5; const int maxK = 2505; const int B = 447; int n, r, q; vvi adj(maxN); vi regof(maxN); vvi timing(maxK); vi st(maxN), en(maxN); vvi reg(maxK); vector<bool> heavy(maxK); unordered_map<int, int> cont; unordered_map<int, int> ansforheavy[maxK]; int tim, hvy; void dfs(int node){ st[node] = tim++; if (heavy[regof[node]]){ cont[regof[node]]++; } timing[regof[node]].push_back(st[node]); for (int x:adj[node]){ for (auto y:cont){ ansforheavy[regof[x]][y.ft] += y.sd; } dfs(x); } en[node] = tim; if (heavy[regof[node]]){ cont[regof[node]]--; } } ll query(int r1, int r2){ if (heavy[r1]) return ansforheavy[regof[r2]][regof[r1]]; else { ll ans = 0; for (int x:reg[r1]){ ans += lower_bound(all(timing[r2]), en[x])-upper_bound(all(timing[r2]), st[x]); } return ans; } } void solve(){ cin>>n>>r>>q; cin>>regof[1]; reg[regof[1]].push_back(1); for (int i = 2;i<=n;i++){ int p; cin>>p>>regof[i]; reg[regof[i]].push_back(i); if (sz(reg[regof[i]])>B+1) reg[regof[i]].pop_back(); adj[p].push_back(i); } for (int i = 1;i<=r;i++){ if (sz(reg[i])>B){ heavy[i] = true; } } dfs(1); while(q--){ int r1, r2; cin>>r1>>r2; cout<<query(r1, r2)<<endl; } } int main() { // ios_base::sync_with_stdio(false); // cin.tie(nullptr); // cout.tie(nullptr); // #ifndef ONLINE_JUDGE // freopen("input.in", "r", stdin); // freopen("output.out", "w", stdout); // freopen("debug.dbg", "w", stderr); // int tt = clock(); // #endif int t=1, i = 1; // cin>>t; while(t--){ // cout<<"Case #"<<i++<<": "; solve(); cout<<'\n'; } // #ifndef ONLINE_JUDGE // cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl; // tt = clock(); // #endif }

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

regions.cpp: In function 'int main()':
regions.cpp:176:14: warning: unused variable 'i' [-Wunused-variable]
  176 |     int t=1, i = 1;
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...