Submission #720283

#TimeUsernameProblemLanguageResultExecution timeMemory
720283bLICToll (BOI17_toll)C++17
Compilation error
0 ms0 KiB
/** * Author: Anil Byar **/ #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; // template<class T> // using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)(x).size() #define uniq(v) v.erase(unique(all(v)), v.end()) #define ft first #define sd second #define pb push_back // Source: https://codeforces.com/blog/entry/68809 // { start void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef DEVAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif // } end typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef vector<vl> vvl; #define dbg if(0) const ll MOD = 1e9+7; const ll MOD9 = 998244353; const ll INFLL = 1e18+5; const int INF = 1e9; void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;} ll power(ll x, ll y, ll mod){if (y==0) return 1;ll ret = power(x, y/2, mod);ret *= ret;ret%=mod;if (y&1) ret *= x;return ret%mod;} ll modinv(ll x, ll mod = MOD) {return power(x, mod-2, mod);} template<class T> istream& operator>>(istream&in, vector<T>&v){ for (T& x:v) in>>x; return in; } template<class T> ostream& operator<<(ostream&out, vector<T>&v){ for (T& x:v) out<<x<<' '; cout<<'\n'; return out; } // use ?: with brackets (?:) // check for overflow // think about dp // Read the statement carefully const int maxN = 1e5+5;; const int maxK = 8001; template<class T> class Div_Con{ vector<vector<T>> table; vector<T> a; T id; int n; public: void init(vector<T> _a, T _id){ n = 1;while((1<<n)<(int)_a.size()) n++; id = _id;a = _a;a.resize(1<<n, id); table.resize(1<<n, vector<T>(n, id)); build(0, (1<<n), n-1); } void build(int l, int r, int lvl){ if (lvl<0) return; int mid = (l+r)/2; table[mid-1][lvl] = a[mid-1]; table[mid][lvl] = a[mid]; for (int i = mid-2;i>=l;i--) table[i][lvl] = comb(a[i], table[i+1][lvl]); for (int i = mid+1;i<r;i++) table[i][lvl] = comb(table[i-1][lvl], a[i]); build(l, mid, lvl-1); build(mid, r, lvl-1); } T comb(T x, T y) {return x+y;} // replace with any associative operation T query(int l, int r){ if (l==r) return a[l]; int lvl = 31 - __builtin_clz(l^r); if (r<l) return Node(5); assert(r>l); // debug(table[l][lvl]); return comb(table[l][lvl], table[r][lvl]); } }; struct Node{ vvl cost; int K; Node(){} Node(int k){ cost.assign(k, vl(k, INFLL)); K = k; for (int i = 0;i<K;i++){ for (int j = 0;j<K;j++) cost[i][j] = INFLL; } } friend Node operator+(Node& a, Node& b){ Node tmp(a.K); for (int i = 0;i<a.K;i++){ for (int j = 0;j<a.K;j++){ for (int l = 0;l<a.K;l++) tmp.cost[i][j] = min(tmp.cost[i][j], a.cost[i][l]+b.cost[l][j]); } } return tmp; } }; void solve(){ int k, n, m, o; cin>>k>>n>>m>>o; Div_Con<Node> divc; vector<Node> nodes(n/k+5, Node(k)); for (int i = 0;i<m;i++){ int a, b, t;cin>>a>>b>>t; assert(a/k<=n/k+1); assert(k); nodes[a/k].cost[a%k][b%k] = t; } divc.init(nodes, Node(k)); // for (int i = 0;) while(o--){ int l, r; cin>>l>>r; if (l/k>=r/k){ cout<<-1; continue; } ll ans = divc.query(l/k, r/k-1).cost[l%k][r%k]; if (ans==INFLL) ans = -1; cout<<ans<<'\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // #ifndef DEVAL // freopen("input.in", "r", stdin); // freopen("output.out", "w", stdout); // freopen("debug.dbg", "w", stderr); // int tt = clock(); // #endif int t=1, i = 1; // cin>>t; while(t--){ // cout<<"Case #"<<i++<<": "; solve(); cout<<'\n'; } // #ifndef DEVAL // cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl; // tt = clock(); // #endif }

Compilation message (stderr)

toll.cpp: In member function 'T Div_Con<T>::query(int, int)':
toll.cpp:126:25: error: there are no arguments to 'Node' that depend on a template parameter, so a declaration of 'Node' must be available [-fpermissive]
  126 |         if (r<l) return Node(5);
      |                         ^~~~
toll.cpp:126:25: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
toll.cpp: In function 'int main()':
toll.cpp:193:14: warning: unused variable 'i' [-Wunused-variable]
  193 |     int t=1, i = 1;
      |              ^
toll.cpp: In instantiation of 'T Div_Con<T>::query(int, int) [with T = Node]':
toll.cpp:175:39:   required from here
toll.cpp:126:29: error: expected primary-expression
  126 |         if (r<l) return Node(5);
      |                         ~~~~^~~