oj.uz

Submission #1082511

# Submission time Handle Problem Language Result Execution time Memory
1082511 2024-08-31T14:14:16 Z vjudge1 Construction of Highway (JOI18_construction) C++17
7 / 100
 2000 ms 604 KB 
#include<bits/stdc++.h>
#define INF 1e18
#define fi first
#define se second
#define FOR(i, k, n) for(ll i = k; i <= n; i++)
#define FOR1(i, k, n) for(ll i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "BAI1.inp"
#define output "BAI1.out"
#define rf 	freopen(input, "r", stdin); freopen(output, "w", stdout)
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int base = 29;
void add(int &a, int b) 
{
	a += b; 
	if(a >= mod) a -= mod; 
	if(a < 0) a += mod; 
}
int par[maxn];
int a[maxn];
int main()
{
	fastio;
	int n;
	cin >> n;
	FOR(i, 1, n)
		cin >> a[i];
	FOR(i, 1, n - 1)
	{
		int u, v;
		cin >> u >> v;
		vi vv;
		par[v] = u;
		while(u != 1)
		{
			vv.pb(u);
			u = par[u];
		}
		vv.pb(1);
		reverse(vv.begin(), vv.end());
		if(vv.size() == 1)
			cout << "0\n";
		else
		{
			int cnt = 0;
			FOR(i, 0, vv.size() - 2)
				FOR(j, i + 1, vv.size() - 1)
					if(a[vv[j]] < a[vv[i]])
						cnt++;
			cout << cnt << "\n";
		}
		for(auto x : vv)
			a[x] = a[v];
	}
	re;
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:5:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, k, n) for(ll i = k; i <= n; i++)
......
   57 |    FOR(i, 0, vv.size() - 2)
      |        ~~~~~~~~~~~~~~~~~~~            
construction.cpp:57:4: note: in expansion of macro 'FOR'
   57 |    FOR(i, 0, vv.size() - 2)
      |    ^~~
construction.cpp:5:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, k, n) for(ll i = k; i <= n; i++)
......
   58 |     FOR(j, i + 1, vv.size() - 1)
      |         ~~~~~~~~~~~~~~~~~~~~~~~       
construction.cpp:58:5: note: in expansion of macro 'FOR'
   58 |     FOR(j, i + 1, vv.size() - 1)
      |     ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 23 ms 604 KB Output is correct
9 Correct 22 ms 488 KB Output is correct
10 Correct 22 ms 348 KB Output is correct
11 Correct 6 ms 484 KB Output is correct
12 Correct 6 ms 348 KB Output is correct
13 Correct 6 ms 348 KB Output is correct
14 Correct 6 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 6 ms 348 KB Output is correct
20 Correct 7 ms 348 KB Output is correct
21 Correct 6 ms 348 KB Output is correct
22 Correct 0 ms 472 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 22 ms 480 KB Output is correct
27 Correct 7 ms 480 KB Output is correct
28 Correct 6 ms 348 KB Output is correct
29 Correct 6 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 8 ms 348 KB Output is correct
33 Correct 2 ms 344 KB Output is correct
34 Correct 2 ms 348 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 2 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 2 ms 348 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 2 ms 348 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 23 ms 604 KB Output is correct
9 Correct 22 ms 488 KB Output is correct
10 Correct 22 ms 348 KB Output is correct
11 Correct 6 ms 484 KB Output is correct
12 Correct 6 ms 348 KB Output is correct
13 Correct 6 ms 348 KB Output is correct
14 Correct 6 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 6 ms 348 KB Output is correct
20 Correct 7 ms 348 KB Output is correct
21 Correct 6 ms 348 KB Output is correct
22 Correct 0 ms 472 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 22 ms 480 KB Output is correct
27 Correct 7 ms 480 KB Output is correct
28 Correct 6 ms 348 KB Output is correct
29 Correct 6 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 8 ms 348 KB Output is correct
33 Correct 2 ms 344 KB Output is correct
34 Correct 2 ms 348 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 2 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 2 ms 348 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 2 ms 348 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 2 ms 348 KB Output is correct
47 Correct 2 ms 576 KB Output is correct
48 Correct 2 ms 520 KB Output is correct
49 Execution timed out 2041 ms 344 KB Time limit exceeded
50 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 23 ms 604 KB Output is correct
9 Correct 22 ms 488 KB Output is correct
10 Correct 22 ms 348 KB Output is correct
11 Correct 6 ms 484 KB Output is correct
12 Correct 6 ms 348 KB Output is correct
13 Correct 6 ms 348 KB Output is correct
14 Correct 6 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 6 ms 348 KB Output is correct
20 Correct 7 ms 348 KB Output is correct
21 Correct 6 ms 348 KB Output is correct
22 Correct 0 ms 472 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 22 ms 480 KB Output is correct
27 Correct 7 ms 480 KB Output is correct
28 Correct 6 ms 348 KB Output is correct
29 Correct 6 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 8 ms 348 KB Output is correct
33 Correct 2 ms 344 KB Output is correct
34 Correct 2 ms 348 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 2 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 2 ms 348 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 2 ms 348 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 2 ms 348 KB Output is correct
47 Correct 2 ms 576 KB Output is correct
48 Correct 2 ms 520 KB Output is correct
49 Execution timed out 2041 ms 344 KB Time limit exceeded
50 Halted 0 ms 0 KB -