Блог пользователя pakaka191

Автор pakaka191, история, 4 года назад, По-русски

include <bits/stdc++.h>

using namespace std;

int main() { int n, s, f; cin >> n >> s >> f; int g[n][n]; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> g[i][j]; } } s--; f--; int m[n]; int r[n]; for(int i = 0; i < n; i++){ m[i] = 0; r[i] = 1e9; } r[s] = 0; while(1){ int v = -1; int e = 2e9; for(int i = 0; i < n; i++){ if(m[i] == 0 && r[i] < e){ e = r[i]; v = i; } } if(v == -1) break; for(int j = 0; j < n; j++){ if(g[v][j] != -1 && m[j] == 0 && r[v] + g[v][j] < r[j]){ r[j] = r[v] + g[v][j]; } } m[v] = 1; } if(r[f] == 1e9) cout << -1; else cout << r[f]; }

Полный текст и комментарии »

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

Автор pakaka191, история, 4 года назад, По-русски

include <bits/stdc++.h>

using namespace std;

int a[100000],d[400000];

void build(int n, int l, int r) { if (l==r) { d[n]=a[l]; return; } int mid=(l+r)/2; build(2*n+1,l,mid); build(2*n+2,mid+1,r); d[n]=__gcd(d[2*n+1],d[2*n+2]); }

int fnd(int n, int l, int r, int L, int R) { if (L==l && R==r) return d[n]; int mid=(l+r)/2; if (R<=mid) return fnd(2*n+1,l,mid,L,R); if (L>mid) return fnd(2*n+2,mid+1,r,L,R); return __gcd(fnd(2*n+1,l,mid,L,mid),fnd(2*n+2,mid+1,r,mid+1,R)); }

void update(int n, int l, int r, int p, int x) { if (l==r) { d[n]=x; a[p]=x; return; } int mid=(l+r)/2; if (p<=mid) update(2*n+1,l,mid,p,x); else update(2*n+2,mid+1,r,p,x); d[n]=__gcd(d[2*n+1],d[2*n+2]); }

int main() { int n; cin >> n; for (int i=0;i<n;i++) cin >> a[i]; build(0,0,n-1); int q; cin >> q; for (int i=0;i<q;i++) { int t,a,b; cin >> t >> a >> b; if (t==1) { cout << fnd(0,0,n-1,a-1,b-1) << endl; } else { update(0,0,n-1,a-1,b); } } }

Полный текст и комментарии »

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится