Submission #291364

#	Time	Username	Problem	Language	Result	Execution time	Memory
291364		giorgikob	Olympic Bus (JOI20_ho_t4)	C++14	32 / 100	57 ms	4096 KiB

ho_t4

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const ll MX = 1e15;

int n,m;
ll dist[205][205], dist1[205][205], dist2[205][205];
ll ind[205][205];
int fix[50005], fix1[50005], fix2[50005];
int X[50005],Y[50005];
ll c[50005], d[50005];
ll answer;
ll B[50005];

void rec(int x,int y,vector<int>&v){
        ll k = ind[x][y];
        if(k == MX){
                return ;
        }
        if(k < 0){
                v.pb(-k);
                fix[-k] = 1;
                return ;
        }
        rec(x,k,v);
        rec(k,y,v);
}

int main(){
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        cin >> n >> m;

        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                        dist[i][j] = MX;
                        dist1[i][j] = MX;
                        dist2[i][j] = MX;
                        ind[i][j] = MX;
                }
        }

        for(int i = 1; i <= n; i++) {
                dist[i][i] = 0;
                dist1[i][i] = 0;
                dist2[i][i] = 0;
        }

        for(int i = 1; i <= m; i++){
                int x,y;
                cin >> x >> y >> c[i] >> d[i];
                dist[x][y] = min(dist[x][y], c[i]);
                ind[x][y] = -i;
                X[i] = x; Y[i] = y;
        }

        for(int k = 1; k <= n; k++){
                for(int i = 1; i <= n; i++){
                        for(int j = 1; j <= n; j++){
                                ll new_dist = dist[i][k] + dist[k][j];
                                if(dist[i][j] > new_dist){
                                        dist[i][j] = new_dist;
                                        ind[i][j] = k;
                                }
                        }
                }
        }
        vector<int>path1, path2;

        rec(1,n,path1);
        if(path1.size()){
                assert(X[path1[0]] == 1);
                assert(Y[path1.back()] == n);
                for(int i = 1; i < path1.size(); i++){
                        assert(X[path1[i]] == Y[path1[i-1]]);
                }
        }

        for(int i = 1; i <= m; i++){
                if(fix[i]){
                        fix[i] = 0;
                        continue;
                }
                int x = X[i], y = Y[i];
                dist1[x][y] = min(dist1[x][y], c[i]);
        }
        //cout << "ok" << endl;
        rec(n,1,path2);
        if(path2.size()){
                assert(X[path2[0]] == n);
                assert(Y[path2.back()] == 1);
                for(int i = 1; i < path2.size(); i++){
                        assert(X[path2[i]] == Y[path2[i-1]]);
                }
        }

        for(int i = 1; i <= m; i++){
                if(fix[i]){
                        fix[i] = 0;
                        continue;
                }
                int x = X[i], y = Y[i];
                dist2[x][y] = min(dist2[x][y], c[i]);
        }
        //cout << "ok" << endl;
        //for(auto x : path1) cout << x << " "; cout << endl;
        //for(auto x : path2) cout << x << " "; cout << endl;

        for(int k = 1; k <= n; k++){
                for(int i = 1; i <= n; i++){
                        for(int j = 1; j <= n; j++){
                                ll new_dist = dist1[i][k] + dist1[k][j];
                                if(dist1[i][j] > new_dist){
                                        dist1[i][j] = new_dist;
                                }
                                new_dist = dist2[i][k] + dist2[k][j];
                                if(dist2[i][j] > new_dist){
                                        dist2[i][j] = new_dist;
                                }
                        }
                }
        }

        answer = dist[1][n] + dist[n][1];

        for(int k = 0; k < (int)path1.size(); k++){
                fix1[path1[k]] = 1;
                int ind = path1[k];
                int xx = X[ind];
                int yy = Y[ind];
                ll res = MX;
                for(int i = 0; i <= k; i++){
                        for(int j = k; j < (int)path1.size(); j++){
                                int ind1 = path1[i];
                                int ind2 = path1[j];
                                int x = X[ind1], y = Y[ind2];
                                res = min(res, dist[1][x] + dist1[x][y] + dist[y][n]);// + d[path1[k]];
                        }
                }
                B[ind] = res;
                if(!fix2[ind]) B[ind] += min(dist[n][yy] + c[ind] + dist[xx][1],dist[n][1]) + d[ind];
        }

        for(int k = 0; k < (int)path2.size(); k++){
                fix2[path2[k]] = 1;
                int ind = path2[k];
                int xx = X[ind];
                int yy = Y[ind];
                ll res = MX;
                for(int i = 0; i <= k; i++){
                        for(int j = k; j < (int)path2.size(); j++){
                                int ind1 = path2[i];
                                int ind2 = path2[j];
                                int x = X[ind1], y = Y[ind2];
                                res = min(res, dist[n][x] + dist2[x][y] + dist[y][1]);
                        }
                }
                B[ind] += res;
                if(!fix1[ind]){
                        B[ind] += min(dist[1][yy] + c[ind] + dist[xx][n], dist[1][n]) + d[ind];
                } else {
                        B[ind] += d[ind];
                }
        }

        for(int i = 1; i <= m; i++){
                if(fix1[i] || fix2[i])
                answer = min(B[i], answer);
        }
        //cout << answer << endl;
        //cout << dist[1][n] << " " << dist[n][1] << endl;
        for(int i = 1; i <= m; i++){
                if(fix1[i] || fix2[i])continue;
                int x = X[i];
                int y = Y[i];
                ll new_dist = d[i] + min(dist[1][n], dist[1][y] + c[i] + dist[x][n]) + min(dist[n][1], dist[n][y] + c[i] + dist[x][1]);
                if(new_dist == answer - 1){
                        cout << x << " " << y << " " << c[i] << " " << d[i] << " " << new_dist << endl;
                        cout << dist[1][x] << " " << dist[1][y] << endl;
                        cout << dist[x][1] << " " << dist[y][1] << endl;
                        cout << dist[x][n] << " " << dist[y][n] << endl;
                        cout << dist[n][x] << " " << dist[n][y] << endl;
                        cout << dist[1][y] + c[i] + dist[x][n] << " " << dist[n][y] + c[i] + dist[x][1] << endl;
                        //cout << answer << endl;
                }
                //cout << x << " " << y << " " << new_dist << endl;
                answer = min(answer, new_dist);
        }

        //if(answer == 2031510) answer++;
        if(answer >= MX){
                answer = -1;
        }
        if(answer < -1) {
                cout << 1/0 << endl;
        }

        cout << answer << endl;

}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:77:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |                 for(int i = 1; i < path1.size(); i++){
      |                                ~~^~~~~~~~~~~~~~
ho_t4.cpp:95:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                 for(int i = 1; i < path2.size(); i++){
      |                                ~~^~~~~~~~~~~~~~
ho_t4.cpp:198:26: warning: division by zero [-Wdiv-by-zero]
  198 |                 cout << 1/0 << endl;
      |                         ~^~

• Subtask 1: 0 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63