제출 #206138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
206138		GioChkhaidze	Construction of Highway (JOI18_construction)	C++14	100 / 100	1131 ms	30684 KiB

construction

#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);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84