Submission #1059010

#TimeUsernameProblemLanguageResultExecution timeMemory
1059010jamjanekCity (JOI17_city)C++14
8 / 100
259 ms43156 KiB
#include "Encoder.h" #include<bits/stdc++.h> using namespace std; vector<int>graf[250010]; int preorder[250010], post[250010], preit, postit; void dfs(int x, int o){ preorder[x]=preit++; for(auto j: graf[x]) if(j!=o) dfs(j, x); post[x]=preit; } long long sumyp[250010]; void Encode(int n, int A[], int B[]) { int i; for(i=0;i<n-1;i++){ graf[A[i]].push_back(B[i]); graf[B[i]].push_back(A[i]); } for(i=1;i<=250000;i++){ sumyp[i] = sumyp[i-1]+(250000-i+1); } dfs(0,-1); for (int i = 0; i < n; ++i) { Code(i, sumyp[preorder[i]]+post[i]-preorder[i]); } }
#include "Device.h" #include<bits/stdc++.h> using namespace std; long long sumypD[250010]; void InitDevice() { int n=250000; for(int i=1;i<=n;i++){ sumypD[i] = sumypD[i-1]+(n-i+1); } sumypD[250000]=1000000000000000000; } pair<int,int> zamien(long long x){ int a = int(upper_bound(sumypD, sumypD+250001, x)-sumypD); a--; return {a, x-sumypD[a]+a}; } int Answer(long long S, long long T) { int X1,X2; int Y1,Y2; X1 = zamien(S).first; X2 = zamien(S).second; Y1 = zamien(T).first; Y2 = zamien(T).second; // printf("%lld\n", sumypD[0]); // cerr<<X1<<" "<<X2<<" "<<Y1<<" "<<Y2<<" "<<S<<" "<<T<<"\n"; if(X1<=Y1 && X2>=Y2)return 1; if(Y1<=X1 && Y2>=X2)return 0; return 2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...