제출 #293169

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
293169	2020-09-07 17:22:15	Berted	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	170 ms	14640 KiB

roadsideadverts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#define pii pair<int,int>
#define mkp make_pair
#define fst first
#define snd second
#define vpi vector<pii>
#define epb emplace_back
using namespace std;
vector<vpi> adj;vector<int> tmp;
int v,sp[2][50001][20]={},q,h[50001]={},tplca,tplgth,tpa,tpb;
void dfs(int u,int p,int pw,int ht)
{
  sp[0][u][0] = p;sp[1][u][0] = pw;h[u] = ht;
  for (int i=1;i<20;i++)
  {
    if (sp[0][u][i-1]!=-1)
    {
      sp[0][u][i] = sp[0][sp[0][u][i-1]][i-1];
      sp[1][u][i] = sp[1][u][i-1] + sp[1][sp[0][u][i-1]][i-1];
    }
    else {break;}
  }
  for (auto v:adj[u])
  {
    if (v.fst!=p)
    {
      dfs(v.fst,u,v.snd,ht+1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30