Submission #1100196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100196		_8_8_	Treatment Project (JOI20_treatment)	C++17	35 / 100	1627 ms	524288 KiB

treatment

    #include <bits/stdc++.h>
        
    using namespace std;
        
    typedef long long ll;
        
    const int  N = 2e5 + 12, MOD = (int)1e9 + 7;
        
    const ll inf = 1e18;
    ll res = inf, d[N];
    int n, m;
    vector<array<int, 4>> a;
        
    bool cmp(array<int, 4> x, array<int, 4> y) {
        return make_pair(x[1], x[2]) < make_pair(y[1], y[2]);
    }
    vector<int> g[N];
    void test() {
        cin >> n >> m;
        a.resize(m);
        for(int i = 0; i < m; i++) {
            cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3], d[i] = inf;
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < m; j++) {
                if(i == j) continue;
                ll inter = a[i][2] - a[j][1] + 1, val = abs(a[i][0] - a[j][0]);
                if(a[j][1] + val <= a[i][2] + 1) {
                    g[i].push_back(j);
                }
            }
        }
        set<pair<ll, int>> st;
        for(int i = 0; i < m; i++) {    
            if(a[i][1] == 1) {
                d[i] = a[i][3];
                st.insert({d[i], i});
            }
        }
        while(!st.empty()) {
            auto [w, v] = (*st.begin());
            st.erase(st.begin());
            for(int to:g[v]) {
                if(d[to] == inf) {
                    st.erase({d[to], to});
                    d[to] = d[v] + a[to][3];
                    st.insert({d[to], to});
                }
            }
        }
        for(int i = 0; i < m; i++) if(a[i][2] == n){
            res = min(res, d[i] );
        }
        if(res == inf) {
            res = -1;
        }
        cout << res << '\n';
    }
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0); 
        
        int t = 1; 
        // cin >> t;
        
        while(t--) 
            test();
        
        return 0;
    }

Compilation message (stderr)

treatment.cpp: In function 'void test()':
treatment.cpp:27:20: warning: unused variable 'inter' [-Wunused-variable]
   27 |                 ll inter = a[i][2] - a[j][1] + 1, val = abs(a[i][0] - a[j][0]);
      |                    ^~~~~

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