oj.uz

Submission #410010

# Submission time Handle Problem Language Result Execution time Memory
410010 2021-05-21T21:04:31 Z mat_v Robot (JOI21_ho_t4) C++14
34 / 100
 3000 ms 52952 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<ll,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

struct edge{
    int x;
    int boja;
    ll v;
};
ll maks = 1e9;

struct node{
    int cale;
    int x;
    ll v;
};

bool operator < (const node &a, const node &b){
    return a.v < b.v;
}
bool operator > (const node &a, const node &b){
    return a.v > b.v;
}

int n,m;
vector<edge> graf[100005];
map<pii,ll>dist;

bool cmp(edge a, edge b){
    if(a.boja < b.boja)return 1;
    return 0;
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    maks *= maks;
    cin >> n >> m;
    ff(i,1,m){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        graf[a].pb({b,c,d});
        graf[b].pb({a,c,d});
    }

    ff(i,1,n)sort(graf[i].begin(), graf[i].end(), cmp);

    priority_queue<node, vector<node>, greater<node>> pq;

    pq.push({-1,1,0});
    while(!pq.empty()){
        node sta = pq.top();
        pq.pop();
        int last = 0;
        ll sum = 0;
        int koji = sta.x;
        int od = sta.cale;
        od -= n;
        int len = graf[koji].size();
        if(len == 0)continue;
        ff(i,0,len - 1){
            if(graf[koji][i].x == od)continue;
            if(graf[koji][i].boja != graf[koji][last].boja){
                ff(j,last,i-1){
                    ll duz1 = graf[koji][j].v + sta.v;
                    int gde = graf[koji][j].x;
                    if(gde == od)continue;
                    if(dist.find({koji+n,gde}) == dist.end() || dist[{koji+n,gde}] > duz1){
                        dist[{koji+n,gde}] = duz1;
                        pq.push({koji+n,gde,duz1});
                    }
                    duz1 = sta.v + sum - graf[koji][j].v;
                    if(dist.find({koji,gde}) == dist.end() || dist[{koji,gde}] > duz1){
                        dist[{koji,gde}] = duz1;
                        pq.push({koji,gde,duz1});
                    }
                }
                last = i;
                sum = graf[koji][i].v;
            }
            else{
                sum += graf[koji][i].v;
            }
        }
         ff(j,last,len-1){
            ll duz1 = graf[koji][j].v + sta.v;
            int gde = graf[koji][j].x;
            if(gde == od)continue;
            if(dist.find({koji+n,gde}) == dist.end() || dist[{koji+n,gde}] > duz1){
            dist[{koji+n,gde}] = duz1;
                pq.push({koji+n,gde,duz1});
            }
            duz1 = sta.v + sum - graf[koji][j].v;
            if(dist.find({koji,gde}) == dist.end() || dist[{koji,gde}] > duz1){
                dist[{koji,gde}] = duz1;
                pq.push({koji,gde,duz1});
            }
        }
    }
    ll res = maks;
    ff(i,1,2*n){
        if(dist.find({i,n}) != dist.end())res = min(res, dist[{i,n}]);
    }

    if(res < maks)cout << res << "\n";
    else cout << -1 << "\n";

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:58:5: note: in expansion of macro 'ff'
   58 |     ff(i,1,m){
      |     ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:65:5: note: in expansion of macro 'ff'
   65 |     ff(i,1,n)sort(graf[i].begin(), graf[i].end(), cmp);
      |     ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:80:9: note: in expansion of macro 'ff'
   80 |         ff(i,0,len - 1){
      |         ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:83:17: note: in expansion of macro 'ff'
   83 |                 ff(j,last,i-1){
      |                 ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:104:10: note: in expansion of macro 'ff'
  104 |          ff(j,last,len-1){
      |          ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:120:5: note: in expansion of macro 'ff'
  120 |     ff(i,1,2*n){
      |     ^~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2664 KB Output is correct
7 Correct 30 ms 2892 KB Output is correct
8 Correct 17 ms 2884 KB Output is correct
9 Correct 1022 ms 3568 KB Output is correct
10 Correct 700 ms 3400 KB Output is correct
11 Correct 1330 ms 3360 KB Output is correct
12 Correct 409 ms 3140 KB Output is correct
13 Correct 1321 ms 3396 KB Output is correct
14 Correct 1331 ms 3360 KB Output is correct
15 Correct 7 ms 2932 KB Output is correct
16 Correct 23 ms 3288 KB Output is correct
17 Correct 14 ms 3068 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 167 ms 3396 KB Output is correct
20 Correct 9 ms 3020 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1923 ms 31352 KB Output is correct
2 Correct 596 ms 14904 KB Output is correct
3 Execution timed out 3008 ms 52952 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2664 KB Output is correct
7 Correct 30 ms 2892 KB Output is correct
8 Correct 17 ms 2884 KB Output is correct
9 Correct 1022 ms 3568 KB Output is correct
10 Correct 700 ms 3400 KB Output is correct
11 Correct 1330 ms 3360 KB Output is correct
12 Correct 409 ms 3140 KB Output is correct
13 Correct 1321 ms 3396 KB Output is correct
14 Correct 1331 ms 3360 KB Output is correct
15 Correct 7 ms 2932 KB Output is correct
16 Correct 23 ms 3288 KB Output is correct
17 Correct 14 ms 3068 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 167 ms 3396 KB Output is correct
20 Correct 9 ms 3020 KB Output is correct
21 Correct 1923 ms 31352 KB Output is correct
22 Correct 596 ms 14904 KB Output is correct
23 Execution timed out 3008 ms 52952 KB Time limit exceeded
24 Halted 0 ms 0 KB -