Submission #288743

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
288743	2020-09-01 20:30:23	TadijaSebez	Mousetrap (CEOI17_mousetrap)	C++11	100 / 100	1080 ms	202616 KiB

mousetrap

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 <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
const int N=1000050;
vector<int> E[N];
int dp[N],dep[N],n,t,m;
bool on[N];
void DP(int u,int p){
  vector<int> d;
  for(int v:E[u])if(v!=p){
    if(p)dp[v]=dp[u]+E[u].size()-2;
    DP(v,u);
    if(on[v])on[u]=1;
    d.pb(dp[v]);
  }
  sort(d.rbegin(),d.rend());
  if(d.size()>1)dp[u]=d[1];
  dp[u]+=E[u].size()>1;
}
vector<pii> tmp;
void DFS(int u,int p){
  if(u==t)return;
  for(int v:E[u])if(v!=p){
    dep[v]=dep[u]+1;
    if(on[u]&&!on[v])tmp.pb({dep[v],dp[v]+(u==m)});
    else DFS(v,u);
  }
}
bool Check(int mid){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:47:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   mid=top+bot>>1;
      |       ~~~^~~~
mousetrap.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%i %i %i",&n,&t,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:40:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  for(int i=1,u,v;i<n;i++)scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
      |                          ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35