제출 #410296

#제출 시각아이디문제언어결과실행 시간메모리
410296mat_vRobot (JOI21_ho_t4)C++14
0 / 100
181 ms20576 KiB
#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 boja; 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]; vector<pii> pravi[100005]; ll dist[100005]; map<int,ll> dist2[100005]; bool cmp(edge a, edge b){ if(a.boja < b.boja)return 1; return 0; } map<pii,bool>post; int main() { ios_base::sync_with_stdio(false); cin.tie(0); maks *= maks; cin >> n >> m; // n = 1005; // m = 2005; ff(i,1,m){ int a,b,c,d; // a = rnd()%n; // b = rnd()%n; // a++; // b++; // c = rnd()%m; // c++; // d = rnd()%1000000; // if(post[{a,b}]){ // a = (rnd()%n) + 1; // b = (rnd()%n) + 1; // } // post[{a,b}] = post[{b,a}] = 1; 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({0,1,0}); ff(i,2,n)dist[i] = maks; while(!pq.empty()){ node sta = pq.top(); int koji = sta.x; int b = sta.boja; ll vl = sta.v; pq.pop(); int len = graf[koji].size(); if(len == 0)continue; if(b){ if(vl != dist2[koji][b])continue; } else{ if(vl != dist[koji])continue; } int last = 0; ll sum = 0; ff(i,0,len){ if(i == len || graf[koji][i].boja != graf[koji][last].boja){ ff(j,last,i-1){ if(b){ if(b != graf[koji][j].boja)continue; int gde = graf[koji][j].x; if(dist[gde] > vl + sum - graf[koji][j].v){ dist[gde] = vl + sum - graf[koji][j].v; pq.push({0,gde,dist[gde]}); } } else{ ll najm = min(graf[koji][j].v, sum - graf[koji][j].v); int gde = graf[koji][j].x; if(dist[gde] > najm + vl){ dist[gde] = najm + vl; pq.push({0,gde,dist[gde]}); } if(dist2[gde].find(graf[koji][j].boja) == dist2[gde].end() || dist2[gde][graf[koji][j].boja] > vl){ if(1 == 1)continue; dist2[gde][graf[koji][j].boja] = vl; pq.push({graf[koji][j].boja, gde, vl}); } } } last = i; sum = graf[koji][i].v; } else{ sum += graf[koji][i].v; } } } if(dist[n] < maks)cout << dist[n] << "\n"; else cout << -1 << "\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

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:63:5: note: in expansion of macro 'ff'
   63 |     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:82:5: note: in expansion of macro 'ff'
   82 |     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:87:5: note: in expansion of macro 'ff'
   87 |     ff(i,2,n)dist[i] = maks;
      |     ^~
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:105:9: note: in expansion of macro 'ff'
  105 |         ff(i,0,len){
      |         ^~
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:107:17: note: in expansion of macro 'ff'
  107 |                 ff(j,last,i-1){
      |                 ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...