Untitled
unknown
plain_text
a month ago
9.2 kB
1
Indexable
Never
#include<bits/stdc++.h> using namespace std; #define all(v) ((v).begin()),((v).end()) #define sz(v) (v.size()) #define yes cout<<"Yes"<<'\n'; #define no cout<<"No"<<'\n'; #define endl '\n'; #define f(i,j,k) for(long long i=j;i<k;i++) #define fb(i,j,k) for(long long i=j;i>=k;i--) #define fs(i,j,k,p) for(long long i=j;i<k;i+=p) #define fbs(i,j,k,p) for(long long i=j;i>=k;i-=p) #define pb push_back #define ppb pop_back #define mp make_pair #define ff first #define ss second #define pi 3.141592653589793238462 typedef long long ll; typedef unsigned long long ull; typedef long double lld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<vector<ll>> vvll; typedef vector<vector<int>> vvi; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pp ; typedef vector<ll> vll; ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} long long pow(long long a, long long b, long long m) { a %= m; long long res = 1; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } ll mod =1e9+7; void add_divs(ll x, map<ll, ll>&divs){ ll i = 2; while(i * i <= x){ while (x % i == 0){ divs[i]++; x /= i; } i++; } if(x > 1) divs[x]++; } ll n1; ll mrg (ll x ,ll y ) { return x+y; } struct segment_tree { vector<ll> tree; void clear() { tree.clear(); } void init(int num, const vector<ll>& a) { n1 = num; tree.assign(4 * n1, 0ll); build(a); } void build(const vector<ll>& a, int id=0,int ns = 0, int ne = n1-1) { if(ns==ne){ tree[id] = a[ns]; return ; } int l = 2*id+1; int r = l+1; int md = ns+(ne-ns)/2; build(a,l, ns, md); build(a,r, md+1, ne); tree[id] = mrg(tree[l],tree[r]); } ll query(int qs, int qe, int id=0, int ns=0, int ne=n1-1) { if(ns>qe || qs>ne){ return 0; ///infnity } if(qs<=ns && qe>=ne){ return tree[id]; } int l = 2*id+1; int r = l+1; int md = ns+(ne-ns)/2; ll ndl = query(qs, qe, l, ns, md); ll ndr = query(qs, qe,r, md+1,ne); return mrg(ndl,ndr ); } void upd(int pos , int val , int id=0, int ns=0,int ne=n1-1) { if(ns>pos || pos>ne){ return; } if(ns==ne){ tree[id]=val; return ; } int l = 2*id+1; int r = l+1; int md = ns+(ne-ns)/2; upd(pos, val,l, ns, md); upd(pos, val, r, md+1, ne); tree[id] = mrg(tree[l],tree[r]); } } st ; auto bin(long long n,vector<int> &v) { long long i; v.push_back(0); for (i = 1 << 30; i > 0; i = i / 2) { if((n & i) != 0) { v.push_back(1); } else { v.push_back(0); } } return v; } vector<bool> premier(int x) { vector<bool> pre(x+1,0); for(int i=2;i<x+1;i++) { if(!pre[i]) { for(int j=2*i;j<=x;j+=i) { pre[j]=1; } } } return pre; } ll mult(ll a,ll b,ll n) { return((a%n)*(b%n))%n; } ll sum(ll a,ll b,ll n) { return((a%n)+(b%n))%n; } ll sub(ll a,ll b,ll n) { return((a%n)-(b%n)+n)%n; } ll inv(ll a,ll n) { return pow(a,n-2,n); } vector<ll> ff() { int n=61; vector<ll> vv(n+1); vv[0]=2; ll j=2; for (int i=1;i<=n;i++) { vv[i]=0; vv[i]+=vv[i-1]+j; j*=2; } for (int i=1;i<=n;i++) { vv[i]+=vv[i-1]; } return vv; } int xxxxx=2*1000000+1; vector<ll> fact(xxxxx); vector<ll> invfact(xxxxx); void fac(ll n=mod) { fact[0]=fact[1]=1; for (int i =2;i<xxxxx;i++) fact[i]=mult(fact[i-1],i,n); } void invfac(ll n=mod) { invfact[xxxxx-1]=inv(fact[xxxxx-1],n); for (int i =xxxxx-2;i>=0;i--) invfact[i]=mult(invfact[i+1],i+1,n); } ll C(ll k,ll m,ll n=mod) { if ((k>m)||(k<0)) return 0; if (k==0)return 1; return mult(fact[m],mult(invfact[k],invfact[m-k],n),n); } void prep(ll n=mod) { fac(n); invfac(n); } ll A(ll k, ll m, ll n) { if ((k>m)||(k<0)) return 1; return mult(fact[m],invfact[k],n); } #define INF 1000000000000000000 void dijkstra(vector<vector<pp>>& graph, ll source) { ll n = graph.size(); // Number of vertices vector<ll> dist(n, INF); // Initialize distances to infinity priority_queue<pp, vector<pp>, greater<pp>> pq; // Min-heap for priority queue dist[source] = 0; // Distance from source to itself is 0 pq.push({0, source}); // Push the source vertex into the priority queue while (!pq.empty()) { ll u = pq.top().second; // Extract vertex with minimum distance ll d = pq.top().first; // Extracted distance pq.pop(); // Check all neighbors of u for (auto& neighbor : graph[u]) { ll v = neighbor.first; // Neighbor vertex ll w = neighbor.second; // Edge weight from u to v // Relaxation step if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; // Update distance if a shorter path is found pq.push({dist[v], v}); // Push the updated distance and vertex to the priority queue } } } cout << dist[n-1] << endl; /*for (int i = 0; i < n; ++i) { cout << "Shortest distance from source to vertex " << i << " is " << dist[i] << endl; }*/ } bool sortbycond(const pair<int, int>& a, const pair<int, int>& b) { if (a.first != b.first) return (a.first < b.first); else return (a.second > b.second); } int s(int n) { int sum = 0; string ss = to_string(n); for (char c : ss) { sum += c - '0'; } return sum; } int sum(int n) { if (n == 0) return 0; if (n % 10 != 9) return sum(n - 1) + s(n); int k=n/10; return 10*sum(k)+45*(k + 1); } #define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define MOD 1000000007 #define MOD1 998244353 #define INF 1e18 #define nline "\n" #define pb push_back #define ppb pop_back #define mp make_pair #define ff first #define ss second #define PI 3.141592653589793238462 #define set_bits __builtin_popcountll #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() typedef long long ll; typedef unsigned long long ull; typedef long double lld; // typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key #ifndef ONLINE_JUDGE #define debug(x) cerr << #x <<" "; _print(x); cerr << endl; #else #define debug(x) #endif void _print(ll t) {cerr << t;} void _print(string t) {cerr << t;} void _print(char t) {cerr << t;} void _print(lld 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(set <T> v); template <class T, class V> void _print(map <T, V> v); template <class T> void _print(multiset <T> 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(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(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} const int N = 1e6; int mobius[N + 10]; bool prime[N + 1]; void sieve() { int n=1e6; memset(prime, true, sizeof(prime)); for (int p = 2; p * p <= n; p++) { if (prime[p] == true) { for (int i = p * p; i <= n; i += p) prime[i] = false; } } } #define int long long // Function to precompute the Mobius function void precompute_mobius() { for (int i = 1; i <= N; i++) { mobius[i] = 1; } for (int i = 2; i <= N; i++) { if (prime[i]) { for (int j = i; j <= N; j += i) { if (j % (i * i) == 0) { mobius[j] = 0; } else { mobius[j] *= -1; } } } } } struct edge{ int a,b,w; edge() { a=0; b=0; w=0; } edge(int a1,int b1,int w1) { a=a1; b=b1; w=w1; } bool operator <(const edge &other1) { return (w<other1.w); } }; ll c2(ll n) { return (n*(n-1))/2; } void solve() { } signed main() { #ifndef ONLINE_JUDGE freopen("Error.txt", "w", stderr); #endif fastio(); int t; t=1; cin>>t; while(t--) { solve(); } }
Leave a Comment