이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |