제출 #841798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841798		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	70 / 100	1051 ms	16132 KiB

roadsideadverts

#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);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio();
    cin.tie(NULL);
    cout.tie(NULL);
    
    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";
		}
		
	}
}

컴파일 시 표준 에러 (stderr) 메시지

roadsideadverts.cpp: In function 'int main()':
roadsideadverts.cpp:64:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |      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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 0 / 30