Submission #210646

#	Time	Username	Problem	Language	Result	Execution time	Memory
210646		robinrst	경주 (Race) (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include        "algorithm"
#include        "iostream"
#include        "numeric"
#include        "iomanip"
#include        "cstring"
#include        "math.h"
#include        "bitset"
#include        "string"
#include        "vector"
#include        "ctime"
#include        "queue"
#include        "stack"
#include        "map"
#include        "set"

#include        "ext/pb_ds/assoc_container.hpp" // Common file
#include        "ext/pb_ds/tree_policy.hpp" // Including tree_order_statistics_node_update
#include        "ext/pb_ds/detail/standard_policies.hpp"

using namespace std;
using namespace __gnu_pbds;


#define          f first
#define          lgn 25
#define          endl '\n'
#define          sc second
#define          N (int)2e5+5
#define          pb push_back
#define          mod 1000000007
#define          ld long double
#define          vi vector<int>
#define          eb emplace_back
#define          vpii vector<pii>
#define          mii map<int,int>
#define          int long long 
#define          pii pair<int,int>
#define          pq priority_queue
#define          BLOCK (int)sqrt(N)
#define          test(x) while(x--)
#define          all(x) begin(x),end(x)
#define          allr(x) rbegin(x),rend(x)
#define          fo(i,a,n) for(int i=a;i<n;i++)
#define          rfo(i,n,a) for(int i=n;i>=a;i--)
#define          FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define          time() cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n"
#define          PI acos(-1.0)
#define 		 bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > 
OS ;

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

inline void INP()
{
	#ifndef ONLINE_JUDGE
	    freopen("input.txt","r",stdin);   
	    freopen("output.txt","w",stdout);
	#endif 
}

const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n,m,k,q,ans;
string s;
vpii adj;
int in[N],out[N],sz[N],Dep[N],sumNow[N],id[N];
bool big[N];
mii path;

void dfsSize(int  i = 0, int p = -1)
{
	static int clk = 0;
	sz[i] = 1;
	in[i] = ++clk;
	id[clk] = i;

	for( auto j : adj[i] )
	{
		if( j.f != p )
		{
			sumNow[j.f] = sumNow[i] + j.sc;
			Dep[j.f] = Dep[i] + 1;
			dfsSize(j.f , i);
			sz[i] += sz[j.f];
		}
	}
	out[i] = clk;
}

#define z id[k]

void add(int i, int x)
{
	int sum = sumNow[i];
	if( x == -1 ) path[sum] = 0;
	else
	{
		int xx = path[sum];
		if( xx == 0 ) xx = INF;
		path[sum] = min( Dep[i] , xx );
	}
}

void dfs(int i = 0 , int p = -1, bool keep = 0)
{
	int mx = -1, bigChild = -1;

	for( auto j : adj[i] )
	{
		if( j.f != p and mx < sz[j.f] ) mx = sz[j.f] , bigChild = j.f;
	}

	for( auto j : adj[i] ) 
	{
		if( j.f != p and j.f != bigChild ) dfs(j.f , i , 0);
	}

	if( ~bigChild ) dfs(bigChild , i , 1) , big[bigChild] = 1;

	for( auto j : adj[i] )
	{
		if( j.f != p and !big[j.f] )
		{
			fo(k,in[j.f],out[j.f]+1)
			{
				int now =  abs( sumNow[z] - sumNow[i] - m );
				if( path[now] )
				{
					ans = min( ans , path[now] + (Dep[z] - Dep[i]) - Dep[i] );
					// Minus Dep[i] in the end is because we have that added in path[now - k]
				}
			}
			fo(k,in[j.f],out[j.f]+1) add( z , 1);
		}
	}

	add(i ,1);

	// for( auto j : path ) cout << j.f << '-' << j.sc << endl;
	// cout << endl;

	if( path[ sumNow[i] + m ] ) ans = min( ans , path[ sumNow[i] + m ] - Dep[i] ); // Minus Dep[i] beacuse that is already added in path[ sumNow[i] + k]

	if( !keep )
	{
		fo(k,in[i],out[i]+1) add(z , -1);
	}
}

void go()
{
	// cin >> n >> m;
	ans = INF;
	// fo(i,0,n-1)
	// {
	// 	int u , v , w;
	// 	cin >> u >> v >> w;
	// 	adj[u].pb({ v, w} );
	// 	adj[v].pb({ u , w} );
	// }
	dfsSize();
	dfs();

	if( ans == INF ) ans = -1;
	return ans;

}

int best_path (int N, int K, int H[][2], int L[])
{
    n = N, m = K;
    adj.resize(n);
    fo(i,0,n-1)
    {
        adj[H[i][0]].pb(mp(H[i][1], L[i]));
        adj[H[i][1]].pb(mp(H[i][0], L[i]));
    }
    return go();
}

/*int32_t main()
{
	INP(); 
	FAST;     
	int t=1; 
	// cin>>t;
	test(t) go();
}
*/

 

Compilation message (stderr)

race.cpp: In function 'void dfsSize(long long int, long long int)':
race.cpp:87:21: error: no matching function for call to 'begin(std::pair<long long int, long long int>&)'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:105:37: note: candidate: template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)
   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&);
                                     ^~~~~
/usr/include/c++/7/bits/range_access.h:105:37: note:   template argument deduction/substitution failed:
race.cpp:87:21: note:   'std::pair<long long int, long long int>' is not derived from 'const std::valarray<_Tp>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:104:31: note: candidate: template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)
   template<typename _Tp> _Tp* begin(valarray<_Tp>&);
                               ^~~~~
/usr/include/c++/7/bits/range_access.h:104:31: note:   template argument deduction/substitution failed:
race.cpp:87:21: note:   'std::pair<long long int, long long int>' is not derived from 'std::valarray<_Tp>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:87:5: note: candidate: template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])
     begin(_Tp (&__arr)[_Nm])
     ^~~~~
/usr/include/c++/7/bits/range_access.h:87:5: note:   template argument deduction/substitution failed:
race.cpp:87:21: note:   mismatched types '_Tp [_Nm]' and 'std::pair<long long int, long long int>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:58:5: note: candidate: template<class _Container> decltype (__cont.begin()) std::begin(const _Container&)
     begin(const _Container& __cont) -> decltype(__cont.begin())
     ^~~~~
/usr/include/c++/7/bits/range_access.h:58:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::pair<long long int, long long int>]':
race.cpp:87:21:   required from here
/usr/include/c++/7/bits/range_access.h:58:56: error: 'const struct std::pair<long long int, long long int>' has no member named 'begin'
     begin(const _Container& __cont) -> decltype(__cont.begin())
                                                 ~~~~~~~^~~~~
/usr/include/c++/7/bits/range_access.h:48:5: note: candidate: template<class _Container> decltype (__cont.begin()) std::begin(_Container&)
     begin(_Container& __cont) -> decltype(__cont.begin())
     ^~~~~
/usr/include/c++/7/bits/range_access.h:48:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&) [with _Container = std::pair<long long int, long long int>]':
race.cpp:87:21:   required from here
/usr/include/c++/7/bits/range_access.h:48:50: error: 'struct std::pair<long long int, long long int>' has no member named 'begin'
     begin(_Container& __cont) -> decltype(__cont.begin())
                                           ~~~~~~~^~~~~
In file included from /usr/include/c++/7/utility:76:0,
                 from /usr/include/c++/7/algorithm:60,
                 from race.cpp:1:
/usr/include/c++/7/initializer_list:89:5: note: candidate: template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)
     begin(initializer_list<_Tp> __ils) noexcept
     ^~~~~
/usr/include/c++/7/initializer_list:89:5: note:   template argument deduction/substitution failed:
race.cpp:87:21: note:   'std::pair<long long int, long long int>' is not derived from 'std::initializer_list<_Tp>'
  for( auto j : adj[i] )
                     ^
race.cpp:87:21: error: no matching function for call to 'end(std::pair<long long int, long long int>&)'
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:107:37: note: candidate: template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)
   template<typename _Tp> const _Tp* end(const valarray<_Tp>&);
                                     ^~~
/usr/include/c++/7/bits/range_access.h:107:37: note:   template argument deduction/substitution failed:
race.cpp:87:21: note:   'std::pair<long long int, long long int>' is not derived from 'const std::valarray<_Tp>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:106:31: note: candidate: template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)
   template<typename _Tp> _Tp* end(valarray<_Tp>&);
                               ^~~
/usr/include/c++/7/bits/range_access.h:106:31: note:   template argument deduction/substitution failed:
race.cpp:87:21: note:   'std::pair<long long int, long long int>' is not derived from 'std::valarray<_Tp>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:97:5: note: candidate: template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])
     end(_Tp (&__arr)[_Nm])
     ^~~
/usr/include/c++/7/bits/range_access.h:97:5: note:   template argument deduction/substitution failed:
race.cpp:87:21: note:   mismatched types '_Tp [_Nm]' and 'std::pair<long long int, long long int>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:78:5: note: candidate: template<class _Container> decltype (__cont.end()) std::end(const _Container&)
     end(const _Container& __cont) -> decltype(__cont.end())
     ^~~
/usr/include/c++/7/bits/range_access.h:78:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(const _Container&) [with _Container = std::pair<long long int, long long int>]':
race.cpp:87:21:   required from here
/usr/include/c++/7/bits/range_access.h:78:54: error: 'const struct std::pair<long long int, long long int>' has no member named 'end'; did you mean 'second'?
     end(const _Container& __cont) -> decltype(__cont.end())
                                               ~~~~~~~^~~
                                               second
/usr/include/c++/7/bits/range_access.h:68:5: note: candidate: template<class _Container> decltype (__cont.end()) std::end(_Container&)
     end(_Container& __cont) -> decltype(__cont.end())
     ^~~
/usr/include/c++/7/bits/range_access.h:68:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(_Container&) [with _Container = std::pair<long long int, long long int>]':
race.cpp:87:21:   required from here
/usr/include/c++/7/bits/range_access.h:68:48: error: 'struct std::pair<long long int, long long int>' has no member named 'end'; did you mean 'second'?
     end(_Container& __cont) -> decltype(__cont.end())
                                         ~~~~~~~^~~
                                         second
In file included from /usr/include/c++/7/utility:76:0,
                 from /usr/include/c++/7/algorithm:60,
                 from race.cpp:1:
/usr/include/c++/7/initializer_list:99:5: note: candidate: template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)
     end(initializer_list<_Tp> __ils) noexcept
     ^~~
/usr/include/c++/7/initializer_list:99:5: note:   template argument deduction/substitution failed:
race.cpp:87:21: note:   'std::pair<long long int, long long int>' is not derived from 'std::initializer_list<_Tp>'
  for( auto j : adj[i] )
                     ^
race.cpp: In function 'void dfs(long long int, long long int, bool)':
race.cpp:118:21: error: no matching function for call to 'begin(std::pair<long long int, long long int>&)'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:105:37: note: candidate: template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)
   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&);
                                     ^~~~~
/usr/include/c++/7/bits/range_access.h:105:37: note:   template argument deduction/substitution failed:
race.cpp:118:21: note:   'std::pair<long long int, long long int>' is not derived from 'const std::valarray<_Tp>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:104:31: note: candidate: template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)
   template<typename _Tp> _Tp* begin(valarray<_Tp>&);
                               ^~~~~
/usr/include/c++/7/bits/range_access.h:104:31: note:   template argument deduction/substitution failed:
race.cpp:118:21: note:   'std::pair<long long int, long long int>' is not derived from 'std::valarray<_Tp>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:87:5: note: candidate: template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])
     begin(_Tp (&__arr)[_Nm])
     ^~~~~
/usr/include/c++/7/bits/range_access.h:87:5: note:   template argument deduction/substitution failed:
race.cpp:118:21: note:   mismatched types '_Tp [_Nm]' and 'std::pair<long long int, long long int>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:58:5: note: candidate: template<class _Container> decltype (__cont.begin()) std::begin(const _Container&)
     begin(const _Container& __cont) -> decltype(__cont.begin())
     ^~~~~
/usr/include/c++/7/bits/range_access.h:58:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::pair<long long int, long long int>]':
race.cpp:118:21:   required from here
/usr/include/c++/7/bits/range_access.h:58:56: error: 'const struct std::pair<long long int, long long int>' has no member named 'begin'
     begin(const _Container& __cont) -> decltype(__cont.begin())
                                                 ~~~~~~~^~~~~
/usr/include/c++/7/bits/range_access.h:48:5: note: candidate: template<class _Container> decltype (__cont.begin()) std::begin(_Container&)
     begin(_Container& __cont) -> decltype(__cont.begin())
     ^~~~~
/usr/include/c++/7/bits/range_access.h:48:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&) [with _Container = std::pair<long long int, long long int>]':
race.cpp:118:21:   required from here
/usr/include/c++/7/bits/range_access.h:48:50: error: 'struct std::pair<long long int, long long int>' has no member named 'begin'
     begin(_Container& __cont) -> decltype(__cont.begin())
                                           ~~~~~~~^~~~~
In file included from /usr/include/c++/7/utility:76:0,
                 from /usr/include/c++/7/algorithm:60,
                 from race.cpp:1:
/usr/include/c++/7/initializer_list:89:5: note: candidate: template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)
     begin(initializer_list<_Tp> __ils) noexcept
     ^~~~~
/usr/include/c++/7/initializer_list:89:5: note:   template argument deduction/substitution failed:
race.cpp:118:21: note:   'std::pair<long long int, long long int>' is not derived from 'std::initializer_list<_Tp>'
  for( auto j : adj[i] )
                     ^
race.cpp:118:21: error: no matching function for call to 'end(std::pair<long long int, long long int>&)'
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:107:37: note: candidate: template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)
   template<typename _Tp> const _Tp* end(const valarray<_Tp>&);
                                     ^~~
/usr/include/c++/7/bits/range_access.h:107:37: note:   template argument deduction/substitution failed:
race.cpp:118:21: note:   'std::pair<long long int, long long int>' is not derived from 'const std::valarray<_Tp>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:106:31: note: candidate: template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)
   template<typename _Tp> _Tp* end(valarray<_Tp>&);
                               ^~~
/usr/include/c++/7/bits/range_access.h:106:31: note:   template argument deduction/substitution failed:
race.cpp:118:21: note:   'std::pair<long long int, long long int>' is not derived from 'std::valarray<_Tp>'
  for( auto j : adj[i] )
                     ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:97:5: note: candidate: template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])
     end(_Tp (&__arr)[_Nm])
     ^~~
/usr/include/c++/7/bits/range_access.h:97:5: note:   template argument deduction/substitution failed:
race.cpp:118:21: note:   mismatched types '_Tp [_Nm]' and 'std::pair<long long int, long long int>'
  for( auto j : adj[i] )
                     ^
I