Submission #571681

#	Time	Username	Problem	Language	Result	Execution time	Memory
571681		Mounir	Toll (BOI17_toll)	C++14	100 / 100	315 ms	167628 KiB

toll

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define print(x) cout << #x << " est " << x << endl;
#define x first
#define y second
#define int long long
using namespace std;

const int K = 5, N = 1e5, OO = 1e9, B = 17;
struct Chemin {
      int dMin[K][K];

      void init(int a){
            for (int i = 0; i < K; ++i)
                  for (int j = 0; j < K; ++j)
                        dMin[i][j] = a;
      }

      void combine(Chemin left, Chemin right){
            for (int i = 0; i < K; ++i)
                  for (int j = 0; j < K; ++j){
                        dMin[i][j] = OO;
                        for (int k = 0; k < K; ++k)
                              chmin(dMin[i][j], left.dMin[i][k] + right.dMin[k][j]);
                  }
      }
};

Chemin chemins[N][B];


signed main(){  
      int tZone, nNoeuds, nAretes, nReqs; cin >> tZone >> nNoeuds >> nAretes >> nReqs;
      int nZones = ceil(nNoeuds/double(tZone));

      for (int iZone = 0; iZone < nZones; ++iZone)
            chemins[iZone][0].init(OO);

      for (int i = 0; i < nAretes; ++i){
            int source, destination, poids; cin >> source >> destination >> poids;
            swap(source, destination);
            int zoneSource = source/tZone;
            chmin(chemins[zoneSource][0].dMin[source%tZone][destination%tZone], poids);
       //     cout << "c " << chemins[zoneSource][0].dMin[source%tZone][destination%tZone] << endl;
      }

      int pow2 = 2;
      for (int b = 1; b < B; ++b, pow2 *= 2){
            for (int source = nZones - 1; source - pow2 >= 0; --source)
                  chemins[source][b].combine(chemins[source][b - 1], chemins[source - pow2/2][b - 1]);
      }

      for (int iReq = 0; iReq < nReqs; ++iReq){
            int source, dest; cin >> source >> dest;
            swap(source, dest);
            int zoneSource = source/tZone, zoneDest = dest/tZone;
            Chemin cCur; cCur.init(OO);
            for (int i = 0; i < K; ++i)
                  cCur.dMin[i][i] = 0;
           // cout << zoneSource << " " << zoneDest << endl;
            int pow2 = 1;
            for (int i = 0; i < B - 1; ++i)
                  pow2 *= 2;
            for (int b = B - 1; b >= 0; --b, pow2 /= 2){
                //  cout << zoneSource << " " << zoneDest << endl;
                  if (zoneSource - pow2 >= zoneDest){
                     //   if (false)
                       //       cout << "req " << iReq << endl;
                  //      cout << "req " << iReq << " " << b << endl;
                        cCur.combine(cCur, chemins[zoneSource][b]);
                        zoneSource -= pow2;
                  }
            }

            if (cCur.dMin[source%tZone][dest%tZone] < OO)
                  cout << cCur.dMin[source%tZone][dest%tZone] << endl;
            else
                  cout << -1 << endl;
      }
      return 0;   
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44