Submission #891523

#TimeUsernameProblemLanguageResultExecution timeMemory
891523coding_monk3Valley (BOI19_valley)C++17
0 / 100
139 ms38820 KiB
#include <bits/stdc++.h> using namespace std; // Miscellanous #define gc getchar_unlocked #define ll long long #define ull unsigned long long #define si(x) scanf("%d",&x) #define si2(x,y) scanf("%d %d",&x,&y) #define sl(x) scanf("%lld",&x) #define sl2(x,y) scanf("%lld %lld",&x,&y) #define sstr(s) cin >> s #define pi(x) printf("%d\n",x) #define pi2(x,y) printf("%d %d\n",x,y) #define pl(x) printf("%lld\n",x) #define pl2(x,y) printf("%lld %lld\n",x,y) #define ps(s) cout << s << endl #define py printf("YES\n") #define pn printf("NO\n") #define pnl printf("\n") #define pb push_back #define ff first #define ss second #define sz(v) (int)v.size() #define all(v) v.begin(),v.end() #define sortv(v) sort(all(v)) #define revsort(v) sort(v.rbegin(),v.rend()) #define reverse(v) reverse(all(v)) #define alla(arr,sz) arr,arr+sz #define sorta(arr,sz) sort(alla(arr,sz)) #define reversea(arr,sz) reverse(alla(arr,sz)) #define cta(x,v) count(alla(arr,sz),x) #define ct(x,v) count(all(v),x) #define cto(v) count_if(all(v),[] (int a) {return a%2 == 1;}) #define cte(v) count_if(all(v),[] (int a) {return a%2 == 0;}) #define MAX(a,b) a = max(a,b) #define MIN(a,b) a = min(a,b) #define clr(x) memset(x, 0, sizeof(x)) // Loops #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i)) #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i)) #define forc(c,s,e) for (char (c)=(s);(c)<=(e);++(c)) #define forr(i,s,e) for (int (i)=(s);(i)>=(e);--(i)) #define foreach(val,cont) for (auto &(val) : (cont)) #define rep(i,n) loop(i,0,n) #define repn(i,n) loope(i,1,n) // Constants #define PI 3.1415926535897932384626 #define sqr(x) ((x) * 1ll * (x)) const int mod = 1000000007; // Containers typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef pair<string,string> pss; typedef map<int, int> mii; // Input Output #define takei(a) int a; si(a) #define takei2(a,b) int a,b; si2(a,b) #define takel(a) ll a; sl(a) #define takel2(a,b) ll a,b; sl2(a,b) #define takearri0(n,a) vi a(n); rep(i,n) si(a[i]) #define takearri1(n,a) vi a(n+1); a[0] = 0; repn(i,n) si(a[i]) #define takearrl0(n,a) vl a(n); rep(i,n) sl(a[i]) #define takearrl1(n,a) vl a(n+1); a[0] = 0ll; repn(i,n) sl(a[i]) // Debug void _print(int t) {cerr << t;} void _print(ll t) {cerr << t;} void _print(string t) {cerr << t;} void _print(char t) {cerr << t;} void _print(double t) {cerr << t;} void _print(ull t) {cerr << t;} template <class T, class V> void _print(pair <T, V> p); template <class T> void _print(vector <T> v); template <class T> void _print(unordered_set <T> v); template <class T> void _print(unordered_multiset <T> v); template <class T> void _print(set <T> v); template <class T> void _print(multiset <T> v); template <class T, class V> void _print(unordered_map <T, V> v); template <class T, class V> void _print(unordered_multimap <T, V> v); template <class T, class V> void _print(map <T, V> v); template <class T, class V> void _print(multimap <T, V> v); template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";} template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(unordered_multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T, class V> void _print(unordered_multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} #ifndef ONLINE_JUDGE #define deb(x) cerr << #x << " = "; _print(x); cerr << endl; #else #define deb(x) #endif inline string inttostr(ll a){ char x[100]; sprintf(x,"%lld",a); string s = x; return s; } inline ll strtoint(string a){ char x[100]; ll res; strcpy(x,a.c_str()); sscanf(x,"%lld",&res); return res; } inline string getstr(void){ char x[1000005]; scanf("%s",x); string s = x; return s; } inline string uppercase(string s){ int n = sz(s); rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A'; return s; } inline string lowercase(string s){ int n = sz(s); rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a'; return s; } // --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- // Link --> https://oj.uz/problem/view/BOI19_valley #define MAXN 100005 #define LOG 17 int up[MAXN][LOG]; ll upf[MAXN][LOG]; int tin[MAXN], tout[MAXN]; vpii adj[MAXN]; ll d[MAXN], dp[MAXN]; vector<bool> is_shop(MAXN, 0); int root,t; void find_d(int v, int p, int wt) { if(v != root) d[v] = d[p] + wt; for(auto ed : adj[v]) if(ed.ff != p) find_d(ed.ff, v, ed.ss); } ll dfs(int v, int p) { ll ans = LONG_LONG_MAX; for(auto ed : adj[v]) if(ed.ff != p) ans = min(ans, dfs(ed.ff,v)); if(is_shop[v]) ans = d[v]; if(ans != LONG_LONG_MAX) dp[v] = ans - 2*d[v]; else dp[v] = LONG_LONG_MAX; return ans; } void dfs1(int v, int p) { tin[v] = t++; up[v][0] = p; repn(i,LOG-1) up[v][i] = up[up[v][i-1]][i-1]; upf[v][0] = dp[v]; repn(i,LOG-1) upf[v][i] = min(upf[v][i-1], upf[up[v][i-1]][i-1]); for(auto ed : adj[v]) if(ed.ff != p) dfs1(ed.ff, v); tout[v] = t++; } int kth_ancestor(int node, int k) { if(k > d[node]) return -1; for (int i = LOG-1; i >= 0; i--) { if((1<<i) <= k) node = up[node][i] , k -= (1<<i); } return node; } int lca(int a, int b) { if(d[a] < d[b]) swap(a,b); a = kth_ancestor(a, d[a] - d[b]); if(a == b) return a; for (int i = LOG-1; i >= 0; i--) if(up[a][i] != up[b][i]) a = up[a][i], b = up[b][i]; return up[a][0]; } // Return value --> MINIMUM of wt of edges along the path a--b ll query(int a, int b) { int c = lca(a,b); // c --> LCA of a and b ll ans = LONG_LONG_MAX; int k; k = d[a] - d[c] + 1; for (int i = LOG-1; i >= 0; i--) { if((1<<i) <= k) ans = min(ans,upf[a][i]), a = up[a][i] , k -= (1<<i); } k = d[b] - d[c] + 1; for (int i = LOG-1; i >= 0; i--) { if((1<<i) <= k) ans = min(ans,upf[b][i]), b = up[b][i] , k -= (1<<i); } return ans; } bool is_ancestor(int anc, int v) { return tin[anc] <= tin[v] and tout[anc] >= tout[v]; } int main() { takei2(n,m); takei(q); si(root); vvi edges(n); repn(i,n-1) { takei2(u,v); takei(wt); edges[i] = {u,v,wt}; adj[u].pb({v,wt}); adj[v].pb({u,wt}); } while(m--) {takei(c); is_shop[c] = 1;} // Constructing d array d[root] = 0; find_d(root,root,0); // Constructing DP array dfs(root,root); // Precomputation for BINARY LIFTING t = 0; dfs1(root,root); while(q--) { takei2(i,r); int u = edges[i][0] , v = edges[i][1]; if(is_ancestor(u,v)) swap(u,v); if(!is_ancestor(u,r)) cout << "escaped\n"; else { ll ans = query(u,r); if(ans == LONG_LONG_MAX) cout << "oo\n"; else pl(ans + d[r]); } } return 0; } // ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Compilation message (stderr)

valley.cpp: In function 'std::string uppercase(std::string)':
valley.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
valley.cpp:47:18: note: in expansion of macro 'loop'
   47 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
valley.cpp:138:3: note: in expansion of macro 'rep'
  138 |   rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
      |   ^~~
valley.cpp: In function 'std::string lowercase(std::string)':
valley.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
valley.cpp:47:18: note: in expansion of macro 'loop'
   47 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
valley.cpp:144:3: note: in expansion of macro 'rep'
  144 |   rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
      |   ^~~
valley.cpp: In function 'void dfs1(int, int)':
valley.cpp:43:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   43 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
valley.cpp:48:19: note: in expansion of macro 'loope'
   48 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
valley.cpp:188:5: note: in expansion of macro 'repn'
  188 |     repn(i,LOG-1) up[v][i] = up[up[v][i-1]][i-1];
      |     ^~~~
valley.cpp:43:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   43 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
valley.cpp:48:19: note: in expansion of macro 'loope'
   48 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
valley.cpp:191:5: note: in expansion of macro 'repn'
  191 |     repn(i,LOG-1) upf[v][i] = min(upf[v][i-1], upf[up[v][i-1]][i-1]);
      |     ^~~~
valley.cpp: In function 'int main()':
valley.cpp:43:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   43 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
valley.cpp:48:19: note: in expansion of macro 'loope'
   48 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
valley.cpp:252:3: note: in expansion of macro 'repn'
  252 |   repn(i,n-1)
      |   ^~~~
valley.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
valley.cpp:69:30: note: in expansion of macro 'si2'
   69 | #define takei2(a,b) int a,b; si2(a,b)
      |                              ^~~
valley.cpp:248:3: note: in expansion of macro 'takei2'
  248 |   takei2(n,m);
      |   ^~~~~~
valley.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define si(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
valley.cpp:68:25: note: in expansion of macro 'si'
   68 | #define takei(a) int a; si(a)
      |                         ^~
valley.cpp:249:3: note: in expansion of macro 'takei'
  249 |   takei(q); si(root);
      |   ^~~~~
valley.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define si(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
valley.cpp:249:13: note: in expansion of macro 'si'
  249 |   takei(q); si(root);
      |             ^~
valley.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
valley.cpp:69:30: note: in expansion of macro 'si2'
   69 | #define takei2(a,b) int a,b; si2(a,b)
      |                              ^~~
valley.cpp:254:5: note: in expansion of macro 'takei2'
  254 |     takei2(u,v); takei(wt);
      |     ^~~~~~
valley.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define si(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
valley.cpp:68:25: note: in expansion of macro 'si'
   68 | #define takei(a) int a; si(a)
      |                         ^~
valley.cpp:254:18: note: in expansion of macro 'takei'
  254 |     takei2(u,v); takei(wt);
      |                  ^~~~~
valley.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define si(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
valley.cpp:68:25: note: in expansion of macro 'si'
   68 | #define takei(a) int a; si(a)
      |                         ^~
valley.cpp:259:15: note: in expansion of macro 'takei'
  259 |   while(m--) {takei(c); is_shop[c] = 1;}
      |               ^~~~~
valley.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
valley.cpp:69:30: note: in expansion of macro 'si2'
   69 | #define takei2(a,b) int a,b; si2(a,b)
      |                              ^~~
valley.cpp:272:5: note: in expansion of macro 'takei2'
  272 |     takei2(i,r);
      |     ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...