oj.uz

Submission #841792

# Submission time Handle Problem Language Result Execution time Memory
841792 2023-09-02T06:10:00 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 1000 ms 18032 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 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;
map<ll,ll>ctn;
ll pos[50010];
ll pre[50010];
bool was[50010];
ll nom=1;
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]==1)
	{
		cnt+=mp[{p,v}];
		pm[p]=max(pm[p],1);
		pm[v]=2;
	}
}
void bfs(ll v,ll p)
{
	pos[v]=nom;
	nom++;
	was[v]=1;
	pre[pos[v]]=pre[pos[p]]+mp[{v,p}];
	for(int it:g[v])
	{
		if(was[it]==0)
		{
			bfs(it,v);
		}
	}
}
void anomalous_solve()
{
    cin>>n;
    ll q,u,v,c;
    bool BANKAI=1;
    ll st=0;
    for(int i=1;i<n;i++)
    {
    	//cin>>u>>v>>c;
    	scanf("%d%d%d",&u,&v,&c);
    	g[u].push_back(v);
    	g[v].push_back(u);
    	ctn[v]++;ctn[u]++;
    	if(ctn[v]>2 || ctn[u]>2)BANKAI=0;
    	mp[{u,v}]=c;
    	mp[{v,u}]=c;
	}
	cin>>q;
	if(BANKAI==0)
	{
		while(q--)
		{
			tek++;
			scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5);
			//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();
		}
	}
	else
	{
		for(int i=0;i<n;i++)
		{
			if(ctn[i]==1)
			{
				st=i;break;
			}
		}
		bfs(st,0);
		while(q--)
		{
			scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5);
			ll mn=min({pos[a1],pos[a2],pos[a3],pos[a4],pos[a5]});
			ll mx=max({pos[a1],pos[a2],pos[a3],pos[a4],pos[a5]});
			cout<<pre[mx]-pre[mn]<<"\n";
		}
		
	}
}
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();
}

Compilation message

roadsideadverts.cpp: In function 'void anomalous_solve()':
roadsideadverts.cpp:63:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |      scanf("%d%d%d",&u,&v,&c);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:77:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |    scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |    scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 16872 KB Output is correct
2 Correct 101 ms 17976 KB Output is correct
3 Correct 97 ms 17924 KB Output is correct
4 Correct 145 ms 17908 KB Output is correct
5 Correct 102 ms 17788 KB Output is correct
6 Correct 112 ms 18032 KB Output is correct
7 Correct 111 ms 18004 KB Output is correct
8 Correct 95 ms 18024 KB Output is correct
9 Correct 95 ms 18000 KB Output is correct
10 Correct 99 ms 17892 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 14416 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 Correct 129 ms 16872 KB Output is correct
3 Correct 101 ms 17976 KB Output is correct
4 Correct 97 ms 17924 KB Output is correct
5 Correct 145 ms 17908 KB Output is correct
6 Correct 102 ms 17788 KB Output is correct
7 Correct 112 ms 18032 KB Output is correct
8 Correct 111 ms 18004 KB Output is correct
9 Correct 95 ms 18024 KB Output is correct
10 Correct 95 ms 18000 KB Output is correct
11 Correct 99 ms 17892 KB Output is correct
12 Execution timed out 1016 ms 14416 KB Time limit exceeded
13 Halted 0 ms 0 KB -