oj.uz

Submission #66396

# Submission time Handle Problem Language Result Execution time Memory
66396 2018-08-10T11:27:40 Z quoriess Zagrade (COI17_zagrade) C++14
30 / 100
 3000 ms 60744 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3049 ms 1924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 46704 KB Output is correct
2 Correct 1154 ms 57792 KB Output is correct
3 Correct 952 ms 57792 KB Output is correct
4 Correct 1093 ms 57792 KB Output is correct
5 Correct 889 ms 57792 KB Output is correct
6 Correct 1071 ms 57792 KB Output is correct
7 Correct 919 ms 57792 KB Output is correct
8 Correct 1033 ms 57792 KB Output is correct
9 Correct 930 ms 57792 KB Output is correct
10 Correct 2023 ms 60744 KB Output is correct
11 Correct 1103 ms 60744 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3049 ms 1924 KB Time limit exceeded
2 Halted 0 ms 0 KB -