Submission #697053

#	Time	Username	Problem	Language	Result	Execution time	Memory
697053		Cross_Ratio	Treatment Project (JOI20_treatment)	C++14	35 / 100	995 ms	524288 KiB

treatment

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int T[100005];
int L[100005];
int R[100005];
ll C[100005];
vector<vector<array<ll, 2>>> adj;
ll dis[200005];
bool vis[200005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    int i, j;
    for(i=1;i<=M;i++) {
        cin >> T[i] >> L[i] >> R[i] >> C[i];
    }
    //0 is left, 1 is right
    //2i is input, 2i+1 is output
    adj.resize(2*M+2);
    for(i=1;i<=M;i++) {
        adj[2*i].push_back({2*i+1, C[i]});
        if(L[i]==1) adj[0].push_back({2*i, 0});
        if(R[i]==N) adj[2*i+1].push_back({1, 0});
    }
    for(i=1;i<=M;i++) {
        for(j=1;j<=M;j++) {
            if(i==j) continue;
            if(T[i] >= T[j]) {
                int t = T[i] - T[j];
                if(R[j] == N || L[i] <= R[j] - t + 1) {
                    adj[2*j+1].push_back({2*i, 0});
                }
            }
            if(T[i] <= T[j]) {
                int t = T[j] - T[i];
                if(L[i] == 1 || L[i] - 1 + t <= R[j]) {
                    adj[2*j+1].push_back({2*i, 0});
                }
            }
        }
    }
    /*for(i=0;i<=2*M+1;i++) {
        cout << i << " : ";
        for(auto n2 : adj[i]) {
            cout << "(" << n2[0] << ", " << n2[1] << ") ";
        }
        cout << '\n';
    }*/
    for(i=0;i<=2*M+1;i++) dis[i] = INF;
    dis[0] = 0;
    while(true) {
        ll mi = INF, pt = -1;
        for(i=0;i<=2*M+1;i++) {
            if(!vis[i] && mi > dis[i]) {
                mi = dis[i];
                pt = i;
            }
        }
        if(pt==-1) break;
        vis[pt] = true;
        for(auto n2 : adj[pt]) {
            if(dis[n2[0]] > dis[pt] + n2[1]) {
                dis[n2[0]] = dis[pt] + n2[1];
            }
        }
    }
    cout << (dis[1]==INF?-1:dis[1]);
}

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61