제출 #206138

#제출 시각아이디문제언어결과실행 시간메모리
206138GioChkhaidzeConstruction of Highway (JOI18_construction)C++14
100 / 100
1131 ms30684 KiB
#include <bits/stdc++.h> #define ll long long #define F first #define S second using namespace std; const int N=1e5+5; int n,a,b,c,L,R,l,r,co,timer,cnt; int C[N],Root[N],tot[N],in[N],out[N],dep[N],P[N]; pair < ll , int > G[N]; vector < int > v[N]; vector < pair < int , ll > > s; set < pair < pair < int , int > , int > > st; set < pair < pair < int , int > , int > > :: iterator it; void Compress() { vector < int > s; map < int , int > f; for (int i=1; i<=n; i++) s.push_back(C[i]); sort(s.begin(),s.end()); s.erase(unique(s.begin(),s.end()),s.end()); for (int i=0; i<s.size(); i++) f[s[i]]=i+1; for (int i=1; i<=n; i++) C[i]=f[C[i]]; } void Dfs(int x,int p) { tot[x]=1,dep[x]=dep[p]+1,P[x]=p; for (int i=0; i<v[x].size(); i++) if (v[x][i]==p) { swap(v[x][i],v[x][v[x].size()-1]); v[x].pop_back(); break; } for (int i=0; i<v[x].size(); i++) { Dfs(v[x][i],x); tot[x]+=tot[v[x][i]]; if (tot[v[x][0]]<tot[v[x][i]]) swap(v[x][0],v[x][i]); } } void Ufs(int x,int root) { in[x]=++timer,Root[x]=root; for (int i=0; i<v[x].size(); i++) if (!i) Ufs(v[x][i],root); else Ufs(v[x][i],v[x][i]); out[x]=timer; } void Upd(int x,int dl) { while (x<=n) { if (G[x].S!=cnt) G[x].S=cnt,G[x].F=dl; else G[x].F+=dl; x+=(x & -x); } } ll Get(int x) { ll res=0; while (x>0) { if (G[x].S==cnt) res+=G[x].F; x-=(x & -x); } return res; } ll Path(int x,int cost) { ll res=0; vector < pair < int , ll > > s; while (x) { L=in[Root[x]],R=in[x]; while (st.size()) { it=st.lower_bound({{R+1,0},0}); if (it==st.begin()) break; --it; l=(*it).F.F,r=(*it).F.S,co=(*it).S; if (l<L) break; if (R<r) { s.push_back({co,R-l+1}); st.insert({{R+1,r},co}); st.erase(st.find(*it)); } else { s.push_back({co,r-l+1}); st.erase(st.find(*it)); } } st.insert({{L,R},cost}); x=P[Root[x]]; } ++cnt; for (int i=0; i<s.size(); i++) { res+=1LL*s[i].S*Get(s[i].F-1); Upd(s[i].F,s[i].S); } return res; } main ( ){ scanf("%d",&n); for (int i=1; i<=n; i++) scanf("%d",&C[i]); Compress(); int a,b; for (int i=1; i<n; i++) { scanf("%d%d",&a,&b); s.push_back({a,b}); v[a].push_back(b); v[b].push_back(a); } Dfs(1,0); Ufs(1,1); for (int i=0; i<s.size(); i++) { a=s[i].F,b=s[i].S,c=C[b]; printf("%I64d\n",Path(b,c)); } }

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

construction.cpp: In function 'void Compress()':
construction.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) 
                ~^~~~~~~~~
construction.cpp: In function 'void Dfs(int, int)':
construction.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x].size(); i++) 
                ~^~~~~~~~~~~~
construction.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x].size(); i++) {
                ~^~~~~~~~~~~~
construction.cpp: In function 'void Ufs(int, int)':
construction.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x].size(); i++) 
                ~^~~~~~~~~~~~
construction.cpp: In function 'long long int Path(int, int)':
construction.cpp:100:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) {
                ~^~~~~~~~~
construction.cpp: At global scope:
construction.cpp:108:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ( ){
        ^
construction.cpp: In function 'int main()':
construction.cpp:127:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) {
                ~^~~~~~~~~
construction.cpp:129:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   printf("%I64d\n",Path(b,c));
                    ~~~~~~~~~^
construction.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
construction.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&C[i]);
   ~~~~~^~~~~~~~~~~~
construction.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...