oj.uz

Submission #841795

# Submission time Handle Problem Language Result Execution time Memory
841795 2023-09-02T06:14:09 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 1000 ms 15356 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;
ll pm[50010];
ll m[50010];
ll n,cnt,a1,a2,a3,a4,a5;
bool used[50010];
vector<ll>g[50010];
ll ctn[50010],pos[50010],pre[50010];
bool was[50010];
ll nom=1;
void dfs(ll v,ll p)
{
	if(m[v]==1)
	{
		pm[v]=1;
	}
	used[v]=1;
	for(int it:g[v])
	{
		if(used[it]!=1)
		{
			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--)
		{
			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;
			for(int i=0;i<n;i++)pm[i]=0,used[i]=0;
		}
	}
	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:60:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |      scanf("%d%d%d",&u,&v,&c);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |    scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |    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 2392 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 15188 KB Output is correct
2 Correct 60 ms 15188 KB Output is correct
3 Correct 73 ms 15188 KB Output is correct
4 Correct 64 ms 15188 KB Output is correct
5 Correct 72 ms 15144 KB Output is correct
6 Correct 59 ms 15184 KB Output is correct
7 Correct 60 ms 15188 KB Output is correct
8 Correct 67 ms 15356 KB Output is correct
9 Correct 66 ms 15184 KB Output is correct
10 Correct 60 ms 15060 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 10380 KB Output is correct
2 Correct 912 ms 14756 KB Output is correct
3 Correct 987 ms 14740 KB Output is correct
4 Correct 871 ms 14704 KB Output is correct
5 Correct 914 ms 14604 KB Output is correct
6 Correct 843 ms 14760 KB Output is correct
7 Correct 941 ms 14840 KB Output is correct
8 Correct 924 ms 14832 KB Output is correct
9 Execution timed out 1018 ms 14784 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 70 ms 15188 KB Output is correct
3 Correct 60 ms 15188 KB Output is correct
4 Correct 73 ms 15188 KB Output is correct
5 Correct 64 ms 15188 KB Output is correct
6 Correct 72 ms 15144 KB Output is correct
7 Correct 59 ms 15184 KB Output is correct
8 Correct 60 ms 15188 KB Output is correct
9 Correct 67 ms 15356 KB Output is correct
10 Correct 66 ms 15184 KB Output is correct
11 Correct 60 ms 15060 KB Output is correct
12 Correct 162 ms 10380 KB Output is correct
13 Correct 912 ms 14756 KB Output is correct
14 Correct 987 ms 14740 KB Output is correct
15 Correct 871 ms 14704 KB Output is correct
16 Correct 914 ms 14604 KB Output is correct
17 Correct 843 ms 14760 KB Output is correct
18 Correct 941 ms 14840 KB Output is correct
19 Correct 924 ms 14832 KB Output is correct
20 Execution timed out 1018 ms 14784 KB Time limit exceeded
21 Halted 0 ms 0 KB -