oj.uz

Submission #841774

# Submission time Handle Problem Language Result Execution time Memory
841774 2023-09-02T05:00:58 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 1000 ms 20564 KB 
/*#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
map<pair<ll,ll>,ll>mp;
map<ll,ll>pm;
ll m[50010];
ll n,cnt,a1,a2,a3,a4,a5;
ll used[50010];
vector<ll>g[50010];
ll tek=0;
void dfs(ll v,ll p)
{
	if(m[v]==1)
	{
		pm[v]=1;
	}
	used[v]=tek;
	for(int it:g[v])
	{
		if(used[it]!=tek)
		{
			dfs(it,v);
		}
	}
	if(pm[v])
	{
		cnt+=mp[{p,v}];
		pm[p]=1;
		pm[v]=0;
	}
}
void anomalous_solve()
{
    cin>>n;
    ll q,u,v,c;
    for(int i=1;i<n;i++)
    {
    	cin>>u>>v>>c;
    	g[u].push_back(v);
    	g[v].push_back(u);
    	mp[{u,v}]=c;
    	mp[{v,u}]=c;
	}
	cin>>q;
	while(q--)
	{
		tek++;
		cin>>a1>>a2>>a3>>a4>>a5;
		m[a2]=m[a3]=m[a4]=m[a5]=1;
		dfs(a1,-1);
		cout<<cnt<<"\n";
		
		m[a2]=m[a3]=m[a4]=m[a5]=0;
		cnt=0;
		pm.clear();
	}
}
int main()
{
	//	freopen("INPUT.txt","r",stdin);
	//  freopen("OUTPUT.txt","w",stdout);

	ios_base::sync_with_stdio();
    cin.tie(NULL);
    cout.tie(NULL);

    ll test=1;
	//cin>>test;
    for(int pos=1;pos<=test;pos++)
    	anomalous_solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct

Subtask #2
0 / 23.0

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

Subtask #3
0 / 40.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Execution timed out 1060 ms 20564 KB Time limit exceeded
3 Halted 0 ms 0 KB -