Submission #209241

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
2092412020-03-13 13:18:00DodgeBallManCat in a tree (BOI17_catinatree)C++14
100 / 100
269 ms32120 KiB
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
int n, t, d, dep[N], sz[N], st[N], en[N], hv[N];
vector<int> g[N];
multiset<int> s;
void dfs( int u, int p ) {
st[u] = ++t, sz[u] = 1, dep[u] = dep[p] + 1;
pii ret( -1e9, -1 );
for( int v : g[u] ) if( v != p ) {
dfs( v, u );
sz[u] += sz[v];
ret = max( ret, pii( sz[v], v ) );
}
hv[u] = ret.y, en[u] = t;
}
void sack( multiset<int> &s, int u, int p ) {
if( hv[u] != -1 ) sack( s, hv[u], u );
multiset<int> t;
for( int v : g[u] ) if( v != p && v != hv[u] ) {
sack( t, v, u );
while( !s.empty() && !t.empty() && *s.begin() + *t.begin() - 2*dep[u] < d ) {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:55:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::multiset<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d",s.size());
                 ~~~~~~~~^
catinatree.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&d);
     ~~~~~^~~~~~~~~~~~~~~
catinatree.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a);
         ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...