oj.uz

Submission #1036090

# Submission time Handle Problem Language Result Execution time Memory
1036090 2024-07-27T03:31:05 Z Phongnv Robot (JOI21_ho_t4) C++14
100 / 100
 305 ms 120832 KB 
///hihi PhongVan cbhk64
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define elif else if
#define el cout << endl
#define pii pair<int, int>
#define mx(x, y) max(x, y)
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define pob pop_back
#define bs binary_search
#define m_p make_pair
#define vii vector<int>
#define int long long
#define getbit(j, i) (j >> i) &1
#define fillchar(a,x) memset(a, x, sizeof (a))
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const long long oo = 1e18;
const int N = 6e5+5;
const int MOD = 1e9+7;
vector< pii > a[N];
map<int , int> mp[N];
vector< pair<int, pii>> g[N];
int dist[N];
int sum[N];
bool vis[N];
void dij(int x)
{
	fo(i,1,N) dist[i] = oo;
	priority_queue< pair < int,int > , vector < pair < int ,int > > , greater < pair < int , int > > > q;
	dist[x] = 0;
	q.push(m_p(0, x));
	while (!q.empty())
	{
		auto p1 = q.top();
		int W = p1.fi;
		int x = p1.se;
		q.pop();
		if (vis[x])
			continue;
		vis[x] = 1;
		for (auto p2 : a[x])
		{
			int y = p2.fi;
			int w = p2.se;
			if (vis[y] || dist[y] < W + w)
				continue;
			dist[y] = W + w;
			q.push({W + w, y});
		}
	}
}
signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen(TASK".inp","r",stdin);
	//freopen(TASK".out","w",stdout);
	int n,m,x,y,c,p;
	cin >> n >> m;
	fo(i,1,m)
	{
		cin >> x >> y >> c >> p;
		g[x].push_back({c, {y, p}});
		g[y].push_back({c, {x, p}});
		a[x].push_back({y, p});
		a[y].push_back({x, p});
	}
	int cur = n;
	fo(i,1,n)
	{
		sort(g[i].begin(), g[i].end());
		for (auto x : g[i])
			sum[x.fi] += x.se.se;
		for (auto x : g[i])
		{
			if (!vis[x.fi])
			{
				++cur;
				a[i].push_back(m_p(cur,0));
			}
			vis[x.fi] = 1;
			a[cur].push_back(m_p(x.se.fi, sum[x.fi] - x.se.se));
			a[x.se.fi].push_back(m_p(cur, 0));
		}
		for (auto x : g[i])
		{
			sum[x.fi] = 0;
			vis[x.fi] = 0;
		}
	}
	dij(1);
	if (dist[n] == oo)
		cout << "-1";
	else
		cout << dist[n];
	return 0;
}

Compilation message

Main.cpp: In function 'void dij(long long int)':
Main.cpp:37:20: warning: iteration 600004 invokes undefined behavior [-Waggressive-loop-optimizations]
   37 |  fo(i,1,N) dist[i] = oo;
      |            ~~~~~~~~^~~~
Main.cpp:7:38: note: within this loop
    7 | #define fo(i, l, r) for(int i = l; i <= r; i++)
......
   37 |  fo(i,1,N) dist[i] = oo;
      |     ~~~~~                             
Main.cpp:37:2: note: in expansion of macro 'fo'
   37 |  fo(i,1,N) dist[i] = oo;
      |  ^~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 61276 KB Output is correct
2 Correct 32 ms 61268 KB Output is correct
3 Correct 25 ms 61528 KB Output is correct
4 Correct 25 ms 61532 KB Output is correct
5 Correct 26 ms 61532 KB Output is correct
6 Correct 25 ms 61552 KB Output is correct
7 Correct 25 ms 61532 KB Output is correct
8 Correct 30 ms 61528 KB Output is correct
9 Correct 34 ms 62044 KB Output is correct
10 Correct 27 ms 62040 KB Output is correct
11 Correct 26 ms 62040 KB Output is correct
12 Correct 26 ms 61972 KB Output is correct
13 Correct 31 ms 62044 KB Output is correct
14 Correct 27 ms 61928 KB Output is correct
15 Correct 30 ms 61784 KB Output is correct
16 Correct 32 ms 62040 KB Output is correct
17 Correct 33 ms 61788 KB Output is correct
18 Correct 29 ms 61780 KB Output is correct
19 Correct 27 ms 62040 KB Output is correct
20 Correct 26 ms 61788 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 82152 KB Output is correct
2 Correct 65 ms 70860 KB Output is correct
3 Correct 138 ms 93040 KB Output is correct
4 Correct 83 ms 74352 KB Output is correct
5 Correct 291 ms 118476 KB Output is correct
6 Correct 299 ms 117804 KB Output is correct
7 Correct 216 ms 111104 KB Output is correct
8 Correct 284 ms 112208 KB Output is correct
9 Correct 271 ms 112024 KB Output is correct
10 Correct 179 ms 94412 KB Output is correct
11 Correct 126 ms 86336 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 61276 KB Output is correct
2 Correct 32 ms 61268 KB Output is correct
3 Correct 25 ms 61528 KB Output is correct
4 Correct 25 ms 61532 KB Output is correct
5 Correct 26 ms 61532 KB Output is correct
6 Correct 25 ms 61552 KB Output is correct
7 Correct 25 ms 61532 KB Output is correct
8 Correct 30 ms 61528 KB Output is correct
9 Correct 34 ms 62044 KB Output is correct
10 Correct 27 ms 62040 KB Output is correct
11 Correct 26 ms 62040 KB Output is correct
12 Correct 26 ms 61972 KB Output is correct
13 Correct 31 ms 62044 KB Output is correct
14 Correct 27 ms 61928 KB Output is correct
15 Correct 30 ms 61784 KB Output is correct
16 Correct 32 ms 62040 KB Output is correct
17 Correct 33 ms 61788 KB Output is correct
18 Correct 29 ms 61780 KB Output is correct
19 Correct 27 ms 62040 KB Output is correct
20 Correct 26 ms 61788 KB Output is correct
21 Correct 112 ms 82152 KB Output is correct
22 Correct 65 ms 70860 KB Output is correct
23 Correct 138 ms 93040 KB Output is correct
24 Correct 83 ms 74352 KB Output is correct
25 Correct 291 ms 118476 KB Output is correct
26 Correct 299 ms 117804 KB Output is correct
27 Correct 216 ms 111104 KB Output is correct
28 Correct 284 ms 112208 KB Output is correct
29 Correct 271 ms 112024 KB Output is correct
30 Correct 179 ms 94412 KB Output is correct
31 Correct 126 ms 86336 KB Output is correct
32 Correct 103 ms 94936 KB Output is correct
33 Correct 112 ms 90824 KB Output is correct
34 Correct 180 ms 99452 KB Output is correct
35 Correct 155 ms 91844 KB Output is correct
36 Correct 197 ms 97192 KB Output is correct
37 Correct 234 ms 108056 KB Output is correct
38 Correct 230 ms 113308 KB Output is correct
39 Correct 131 ms 107644 KB Output is correct
40 Correct 274 ms 113492 KB Output is correct
41 Correct 297 ms 113492 KB Output is correct
42 Correct 268 ms 108508 KB Output is correct
43 Correct 113 ms 86828 KB Output is correct
44 Correct 162 ms 111824 KB Output is correct
45 Correct 248 ms 100896 KB Output is correct
46 Correct 195 ms 97108 KB Output is correct
47 Correct 228 ms 101976 KB Output is correct
48 Correct 305 ms 120832 KB Output is correct