Submission #961864

#TimeUsernameProblemLanguageResultExecution timeMemory
961864vjudge1City Mapping (NOI18_citymapping)C++17
100 / 100
15 ms22104 KiB
#include <bits/stdc++.h> #pragma optimize("Ofast") #pragma target("avx2") using namespace std; #define ll long long #define ld long double #define pb push_back #define pf push_front #define pii pair<int,int> #define all(v) v.begin(),v.end() #define F first #define S second #define mem(a,i) memset(a,i,sizeof(a)) #define sz(s) (int)s.size() #define y1 yy #define ppb pop_back #define lb lower_bound #define ub upper_bound #define gcd(a,b) __gcd(a,b) #define in insert // #define int ll const int MAX=5e5+5; const int block=400; const ll inf=2e18; const int mod=998244353; const int mod1=1e9+9; const ld eps=1e-9; int dx[8]={1,0,-1,0,1,-1,-1,1}; int dy[8]={0,1,0,-1,1,-1,1,-1}; int binpow(int a,int n){ if(!n)return 1; if(n%2==1)return a*binpow(a,n-1)%mod; int k=binpow(a,n/2); return k*k%mod; } #include "citymapping.h" vector<int> g[MAX]; int use[MAX]; ll d[MAX]; int ord[MAX]; int n; bool cmp(int x,int y){ return d[x]<d[y]; } int s[MAX]; int big[MAX]; void build(int v,int p=-1){ s[v]=1; big[v]=0; for(auto to:g[v]){ if(to==p)continue; build(to,v); if(s[to]>s[big[v]])big[v]=to; s[v]+=s[to]; } } void find_roads(int N, int Q, int A[], int B[], int W[]) { n=N; for(int i=2;i<=n;i++){ ord[i]=i; d[i]=get_distance(1,i); } sort(ord+2,ord+n+1,cmp); for(int i=2;i<=n;i++){ for(int j=1;j<=n;j++)use[j]=0; build(1); int cur=1; int f=ord[i]; ll d1=d[f]; vector<int> P; bool was=0; for(int j=0;j<=10;j++){ vector<int> vec; int curv=cur; while(curv){ vec.pb(curv); curv=big[curv]; } if(sz(vec)==1){ A[i-2]=vec[0]; B[i-2]=f; W[i-2]=d1; g[vec[0]].pb(f); was=1; // cout<<i-2<<" "<<vec[0]<<" "<<f<<" "<<d1<<"\n"; break; } ll d2=get_distance(vec.back(),f); ll dpr=(d1+d2-(d[vec.back()]-d[vec[0]]))/2; for(int i=0;i<sz(vec);i++){ if(d[f]==dpr+d[vec[i]]){ { bool changed=0; vector<int> can; for(auto to:g[vec[i]]){ if(use[to])continue; if(to!=big[vec[i]]){ can.pb(to); } } if(can.empty())big[vec[i]]=0; else{ big[vec[i]]=can[0]; } for(int j=0;j<sz(vec);j++){ if(i!=j)use[vec[j]]=1; } } d1=dpr; cur=vec[i]; break; } } } } return; }

Compilation message (stderr)

citymapping.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
citymapping.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      | 
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:108:12: warning: unused variable 'changed' [-Wunused-variable]
  108 |       bool changed=0;
      |            ^~~~~~~
citymapping.cpp:86:8: warning: variable 'was' set but not used [-Wunused-but-set-variable]
   86 |   bool was=0;
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...