제출 #392538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
392538		vanic	관광지 (IZhO14_shymbulak)	C++14	0 / 100	49 ms	8792 KiB

shymbulak

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <stack>
#include <map>
#include <vector>
#include <queue>
#include <cstring>
#include <array>
#include <bitset>

using namespace std;

typedef long long ll;

const int maxn=2e5+5, Log=18, pot=(1<<Log);

struct tournament{
	int t[pot*2];
	double k[pot*2];
	int prop[pot*2];
	void propagate(int x){
		if(!prop[x]){
			return;
		}
		t[x]+=prop[x];
		if(x<pot){
			prop[x*2]+=prop[x];
			prop[x*2+1]+=prop[x];
		}
		prop[x]=0;
	}
	void cisti(int L, int D, int x, int val){
		propagate(x);
		if(L==val && D==val){
			return;
		}
		if((L+D)/2>=val){
			cisti(L, (L+D)/2, x*2, val);
		}
		else{
			cisti((L+D)/2+1, D, x*2+1, val);
		}
	}
	void update1(int x, int val, double komb){
		cisti(0, pot-1, 1, x-pot);
		t[x]=val;
		k[x]=komb;
		for(x/=2; x>0; x/=2){
			propagate(x*2);
			propagate(x*2+1);
			if(t[x*2]>t[x*2+1]){
				t[x]=t[x*2];
				k[x]=k[x*2];
			}
			else if(t[x*2]<t[x*2+1]){
				t[x]=t[x*2+1];
				k[x]=k[x*2+1];
			}
			else{
				t[x]=t[x*2];
				k[x]=k[x*2]+k[x*2+1];
			}
		}
	}
	void update(int x, int val){
		t[x]+=val;
		for(x/=2; x>0; x/=2){
			propagate(x*2);
			propagate(x*2+1);
			if(t[x*2]>t[x*2+1]){
				t[x]=t[x*2];
				k[x]=k[x*2];
			}
			else if(t[x*2]<t[x*2+1]){
				t[x]=t[x*2+1];
				k[x]=k[x*2+1];
			}
			else{
				t[x]=t[x*2];
				k[x]=k[x*2]+k[x*2+1];
			}
		}
	}
	void update2(int L, int D, int x, int l, int d, int val){
		propagate(x);
		if(L>=l && D<=d){
			update(x, val);
			if(x<pot){
				prop[x*2]+=val;
				prop[x*2+1]+=val;
			}
			return;
		}
		if((L+D)/2>=l){
			update2(L, (L+D)/2, x*2, l, d, val);
		}
		if((L+D)/2+1<=d){
			update2((L+D)/2+1, D, x*2+1, l, d, val);
		}
	}
};


vector < int > ms[maxn];
bitset < maxn > bio;
vector < int > sad;
vector < int > da;
bitset < maxn > cik;
tournament T;


bool ciklus(int x, int prosl){
	if(bio[x]){
		bool p=0;
		for(int i=0; i<(int)sad.size(); i++){
			if(sad[i]==x){
				p=1;
			}
			if(p){
				da.push_back(sad[i]);
				cik[sad[i]]=1;
			}
		}
		return 1;
	}
	sad.push_back(x);
	bio[x]=1;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			if(ciklus(ms[x][i], x)){
				return 1;
			}
		}
	}
	bio[x]=0;
	sad.pop_back();
	return 0;
}

vector < int > dulj;

void siri(int x, int dep){
//	cout << "proso " << x << endl;
	bio[x]=1;
	dulj.push_back(dep);
	for(int i=0; i<(int)ms[x].size(); i++){
		if(!cik[ms[x][i]] && !bio[ms[x][i]]){
			siri(ms[x][i], dep+1);
		}
	}
}

vector < array < double, 4 > > svi;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int a, b;
	for(int i=0; i<n; i++){
		cin >> a >> b;
		a--;
		b--;
		ms[a].push_back(b);
		ms[b].push_back(a);
	}
	ciklus(0, 0);
	bio.reset();
/*	for(int i=0; i<n; i++){
		if(cik[i]){
			cout << i << ' ';
		}
	}
	cout << endl;*/
	int br1, br2;
	int val1, val2;
	int pos;
	int m=da.size();
	for(int i=0; i<m; i++){
//		cout << da[i] << ' ';
		siri(da[i], 0);
		sort(dulj.begin(), dulj.end());
		br1=0;
		pos=dulj.size()-1;
		val1=dulj.back();
		while(pos>-1 && val1==dulj[pos]){
			br1++;
			pos--;
		}
		if(br1>1){
			svi.push_back({val1, br1, val1, (double)(br1-1)/2});
		}
		else{
			if(pos==-1){
				val2=0;
			}
			else{
				val2=dulj[pos];
			}
			br2=0;
			while(pos>-1 && val2==dulj[pos]){
				br2++;
				pos--;
			}
			br2=max(br2, 1);
			svi.push_back({val1, br1, val2, br2});
		}
		dulj.clear();
	}
//	cout << endl;
/*	for(int i=0; i<m; i++){
		cout << svi[i][0] << ' ' << svi[i][1] << ' ' << svi[i][2] << ' ' << svi[i][3] << endl;
	}*/
	int l1, d1, l2, d2;
	for(int i=0; i<m; i++){
		T.update1(i+pot, svi[i][0], svi[i][1]);
	}
	int maksi=0;
	ll komb=0;
	int val;
	for(int i=0; i<m; i++){
		T.update1(i+pot, svi[i][2], svi[i][3]);
		if(!(m&1) && i<m/2){
			T.update1(i+pot+m/2, svi[i+m/2][0], svi[i+m/2][1]*2);
		}
		if(!i){
			for(int j=1; j<m; j++){
				T.update2(0, pot-1, 1, j, j, min(j, m-j));
			}
		}
		else{
			l1=i-m/2;
			d1=i-1;
			if(l1<0){
				l2=l1+m;
				d2=m-1;
				l1=0;
				T.update2(0, pot-1, 1, l2, d2, 1);
			}
			T.update2(0, pot-1, 1, l1, d1, 1);
			l1=i;
			d1=i+m/2-1;
			if(d1>=m){
				l2=0;
				d2=d1-m;
				d1=m-1;
				T.update2(0, pot-1, 1, l2, d2, -1);
			}
			T.update2(0, pot-1, 1, l1, d1, -1);
		}
		val=T.t[1]+svi[i][0];
//		cout << val << ' ' << svi[i][1] << ' ' << T.k[1] << endl;
		if(val>maksi){
			maksi=val;
			komb=T.k[1]*svi[i][1];
		}
		else if(val==maksi){
			komb+=T.k[1]*svi[i][1];
		}
		T.update1(i+pot, -maxn, 0);
		if(!(m&1) && i<m/2){
			T.update1(i+pot+m/2, svi[i+m/2][0], svi[i+m/2][1]);
		}
	}
	cout << komb << '\n';
//	cout << maksi << endl;
	return 0;
}

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

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:196:19: warning: narrowing conversion of 'val1' from 'int' to 'double' [-Wnarrowing]
  196 |    svi.push_back({val1, br1, val1, (double)(br1-1)/2});
      |                   ^~~~
shymbulak.cpp:196:25: warning: narrowing conversion of 'br1' from 'int' to 'double' [-Wnarrowing]
  196 |    svi.push_back({val1, br1, val1, (double)(br1-1)/2});
      |                         ^~~
shymbulak.cpp:196:30: warning: narrowing conversion of 'val1' from 'int' to 'double' [-Wnarrowing]
  196 |    svi.push_back({val1, br1, val1, (double)(br1-1)/2});
      |                              ^~~~
shymbulak.cpp:211:19: warning: narrowing conversion of 'val1' from 'int' to 'double' [-Wnarrowing]
  211 |    svi.push_back({val1, br1, val2, br2});
      |                   ^~~~
shymbulak.cpp:211:25: warning: narrowing conversion of 'br1' from 'int' to 'double' [-Wnarrowing]
  211 |    svi.push_back({val1, br1, val2, br2});
      |                         ^~~
shymbulak.cpp:211:30: warning: narrowing conversion of 'val2' from 'int' to 'double' [-Wnarrowing]
  211 |    svi.push_back({val1, br1, val2, br2});
      |                              ^~~~
shymbulak.cpp:211:36: warning: narrowing conversion of 'br2' from 'int' to 'double' [-Wnarrowing]
  211 |    svi.push_back({val1, br1, val2, br2});
      |                                    ^~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50