Submission #66396

#	Time	Username	Problem	Language	Result	Execution time	Memory
66396		quoriess	Zagrade (COI17_zagrade)	C++14	30 / 100	3049 ms	60744 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
vector<vector<int> > adj;
const lli MAX=3*1e5+5;
int val(char c){
	if(c=='(')return 1;
	else if(c==')')return -1;
	else return -1123214;
}
bool lookup[1001][1001];
typedef pair<int,int> pii;
typedef pair<char,int> pci;

lli solve(vector<pci>& chain){
	int len=(int)chain.size();
	map<int,int> freq;
	vector<int> dp(MAX,0);
	dp[0]=0;
	lli snc=0;
	set<pii> dset;
	map<int,set<pii> > ipf;
	/*
	 freq ayarla
	 1'den n'e:
		bul'dan küçük olan ilk elemanı bul = gind
		ipf[bul]'da gind'den küçük olanları bul
		bul'u arttır
	 * */
	for (int i = 1; i <= len  ; i++)
	{
		dp[i]=dp[i-1]+val(chain[i-1].first);
		if(ipf.find(dp[i])==ipf.end()){
			ipf[dp[i]]=set<pii>();
		}
		ipf[dp[i]].insert(pii(i,ipf[dp[i]].size()));
		dset.insert(pii(dp[i],i));
	}
	
	int i=1;
	while(dp[i]!=-1&&i<=len){
		if(dp[i]==0&&!lookup[chain[0].second][chain[i-1].second]){
			lookup[chain[0].second][chain[i-1].second]=true;
			snc++;
		}
		i++;
	}
	return snc;
}
/*
4
(())
*/
lli sndc;
void solveDfs(int node,int parent,vector<pci> chainNow,vector<char>& chain){

	chainNow.push_back(pci(chain[node-1],node));
	if(adj[node].size()==1&&adj[node][0]==parent){
		sndc+=solve(chainNow);
	}
	for(auto u:adj[node]){
		if(u==parent)continue;
		solveDfs(u,node,chainNow,chain);
	}
}
lli trueSolve(vector<char>& chain){
	int len=(int)chain.size();
	map<int,int> freq;
	vector<int> dp(MAX,0);
	dp[0]=0;
	int bul=0;
	lli snc=0;
	set<pii> dset;
	map<int,set<pii> > ipf;
	/*
	 freq ayarla
	 1'den n'e:
		bul'dan küçük olan ilk elemanı bul = gind
		ipf[bul]'da gind'den küçük olanları bul
		bul'u arttır
	 * */
	for (int i = 1; i <= len  ; i++)
	{
		dp[i]=dp[i-1]+val(chain[i-1]);
		if(ipf.find(dp[i])==ipf.end()){
			ipf[dp[i]]=set<pii>();
		}
		ipf[dp[i]].insert(pii(i,ipf[dp[i]].size()));
		dset.insert(pii(dp[i],i));
	}
	
	
	map<int,int> freqRem;
	for (int i = 1; i <=len ; i++)
	{
		int gind=0;
		set<pii>::iterator it=dset.lower_bound(pii(bul-1,-1));
		if(it==dset.end()){
			gind=len;
		}
		else if(it->first!=bul-1)gind=len;
		else gind=it->second;
		
		//cout <<"gind: "<< gind<<"\n";
		//gind'den küçük eşitleri bul
		set<pii>::iterator git=ipf[bul].lower_bound(pii(gind+1,-1));
		if(git==ipf[bul].begin()){
			snc+=0;//:)
		}
		else{
			git--;
			//cout << "buldu: "<<git->first<<"-"<<git->second<<"\n";
			snc+=git->second+1-freqRem[bul];
		}
		//cout <<snc<<" snc \n";
		bul+=val(chain[i-1]);		
		set<pii>::iterator sil=ipf[dp[i]].lower_bound(pii(i,-1));
		ipf[dp[i]].erase(sil);
		if(freqRem.find(dp[i])==freqRem.end())freqRem[dp[i]]=0;
		freqRem[dp[i]]++;
		dset.erase(pii(dp[i],i));
	}
	return snc;
	
}
int main(){
	int n;
	cin>>n;
	vector<char> chain(n,0);
	adj=vector<vector<int> >(n+1,vector<int>());
	/*srand(time(0));
	for (int i = 0; i < n; i++)
	{
		chain.push_back(rand()%2?'(':')');
	}*/
	for (int i = 0; i < n; i++)
	{
		cin>>chain[i];
	}
	for (int i = 0; i < n-1; i++)
	{
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	/*for (int i = 0; i < n; i++)
	{
	}
	
	for (int i = n-1; i >=0; i--)
	{
		//cout << chain[i];
	}*/
	//cout<<"\n";
	if(n>1000){
		lli snc=0;
		snc+=trueSolve(chain);
		reverse(chain.begin(),chain.end());
		snc+=trueSolve(chain);
		cout << snc;
	}
	else{
		for (int i = 1; i <=n ; i++)
		{
			solveDfs(i,-1,vector<pci>(),chain);
		}
		cout<<sndc<<"\n";
	}
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60