oj.uz

Submission #378365

# Submission time Handle Problem Language Result Execution time Memory
378365 2021-03-16T15:00:41 Z Bidrift Traffic (IOI10_traffic) C++17
50 / 100
 64 ms 16128 KB 
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <string>
#include <fstream>
#include <list>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <iomanip>
#include "traffic.h"

#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define srt(a) sort(all(a));
#define srtc(a,comp) sort(all(a),comp);
#define srtb(a) sort(a.rbegin(),a.rend());
#define boost ios::sync_with_stdio(false); cin.tie(0); cin.tie(0);
using ll = long long;
using namespace std;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> ii;
typedef vector<ii> vpi;
const int dx[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //right left down up
void setIO(string name = "") { // name is nonempty for USACO file I/O
    ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output
    // alternatively, cin.tie(0)->sync_with_stdio(0);
    freopen((name+".in").c_str(), "r", stdin); // see Input & Output
    freopen((name+".out").c_str(), "w", stdout);
}

vi adj[100005], nodes(100005,0), people(100005,0), children(100005, 0);
int fans = 0;

void DFS(int parent, int avoid){
    for (auto x: adj[parent]){
        if (x == avoid) continue;
        DFS(x,parent);
        children[parent]+= children[x];
        people[parent] = max(people[parent],children[x]);
    }
    people[parent] = max(people[parent], fans-children[parent]-nodes[parent]);
    children[parent] += nodes[parent];
}

int LocateCentre(int n, int p[], int s[], int d[]){
    for (int i = 0; i < n; i++){
        fans += p[i];
        nodes[i] = p[i];
    }
    for (int i = 0; i < n-1; i++){
        adj[s[i]].pb(d[i]);
        adj[d[i]].pb(s[i]);
    }
    DFS(0,-1);
    int ans, mini = INT32_MAX;
    for (int i = 0; i < n; i++){
        if (people[i] < mini){
            ans = i;
            mini = people[i];
        }
    }
    return ans;
}

Compilation message

traffic.cpp: In function 'void setIO(std::string)':
traffic.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   36 |     freopen((name+".in").c_str(), "r", stdin); // see Input & Output
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffic.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:71:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |     return ans;
      |            ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3820 KB Output is correct
2 Correct 3 ms 3820 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 4 ms 3820 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 3 ms 3820 KB Output is correct
7 Correct 3 ms 3820 KB Output is correct
8 Correct 3 ms 3820 KB Output is correct
9 Correct 4 ms 3820 KB Output is correct
10 Correct 3 ms 3820 KB Output is correct
11 Correct 3 ms 3820 KB Output is correct
12 Correct 3 ms 3820 KB Output is correct
13 Correct 3 ms 3820 KB Output is correct
14 Correct 3 ms 3820 KB Output is correct
15 Correct 3 ms 3820 KB Output is correct
16 Correct 3 ms 3820 KB Output is correct
17 Correct 4 ms 3840 KB Output is correct
18 Correct 3 ms 3820 KB Output is correct
19 Correct 3 ms 3820 KB Output is correct
20 Correct 3 ms 3820 KB Output is correct
21 Correct 3 ms 3820 KB Output is correct
22 Correct 3 ms 3820 KB Output is correct
23 Correct 3 ms 3908 KB Output is correct
24 Correct 3 ms 3820 KB Output is correct
25 Correct 3 ms 3820 KB Output is correct
26 Correct 3 ms 3948 KB Output is correct
27 Correct 3 ms 3948 KB Output is correct
28 Correct 3 ms 3948 KB Output is correct
29 Correct 4 ms 3948 KB Output is correct
30 Correct 3 ms 3948 KB Output is correct
31 Correct 3 ms 3948 KB Output is correct
32 Correct 3 ms 3948 KB Output is correct
33 Correct 4 ms 3948 KB Output is correct
34 Correct 3 ms 3820 KB Output is correct
35 Correct 3 ms 3948 KB Output is correct
36 Correct 4 ms 3948 KB Output is correct
37 Correct 4 ms 3948 KB Output is correct
38 Correct 5 ms 3948 KB Output is correct
39 Correct 4 ms 3948 KB Output is correct
40 Correct 4 ms 3948 KB Output is correct
41 Correct 4 ms 3948 KB Output is correct
42 Correct 4 ms 3948 KB Output is correct
43 Correct 4 ms 3820 KB Output is correct
44 Correct 3 ms 3820 KB Output is correct
45 Correct 3 ms 3820 KB Output is correct
46 Correct 4 ms 3820 KB Output is correct
47 Correct 3 ms 3908 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3820 KB Output is correct
2 Correct 3 ms 3820 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 4 ms 3820 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 3 ms 3820 KB Output is correct
7 Correct 3 ms 3820 KB Output is correct
8 Correct 3 ms 3820 KB Output is correct
9 Correct 4 ms 3820 KB Output is correct
10 Correct 3 ms 3820 KB Output is correct
11 Correct 3 ms 3820 KB Output is correct
12 Correct 3 ms 3820 KB Output is correct
13 Correct 3 ms 3820 KB Output is correct
14 Correct 3 ms 3820 KB Output is correct
15 Correct 3 ms 3820 KB Output is correct
16 Correct 3 ms 3820 KB Output is correct
17 Correct 4 ms 3840 KB Output is correct
18 Correct 3 ms 3820 KB Output is correct
19 Correct 3 ms 3820 KB Output is correct
20 Correct 3 ms 3820 KB Output is correct
21 Correct 3 ms 3820 KB Output is correct
22 Correct 3 ms 3820 KB Output is correct
23 Correct 3 ms 3908 KB Output is correct
24 Correct 3 ms 3820 KB Output is correct
25 Correct 3 ms 3820 KB Output is correct
26 Correct 3 ms 3948 KB Output is correct
27 Correct 3 ms 3948 KB Output is correct
28 Correct 3 ms 3948 KB Output is correct
29 Correct 4 ms 3948 KB Output is correct
30 Correct 3 ms 3948 KB Output is correct
31 Correct 3 ms 3948 KB Output is correct
32 Correct 3 ms 3948 KB Output is correct
33 Correct 4 ms 3948 KB Output is correct
34 Correct 3 ms 3820 KB Output is correct
35 Correct 3 ms 3948 KB Output is correct
36 Correct 4 ms 3948 KB Output is correct
37 Correct 4 ms 3948 KB Output is correct
38 Correct 5 ms 3948 KB Output is correct
39 Correct 4 ms 3948 KB Output is correct
40 Correct 4 ms 3948 KB Output is correct
41 Correct 4 ms 3948 KB Output is correct
42 Correct 4 ms 3948 KB Output is correct
43 Correct 4 ms 3820 KB Output is correct
44 Correct 3 ms 3820 KB Output is correct
45 Correct 3 ms 3820 KB Output is correct
46 Correct 4 ms 3820 KB Output is correct
47 Correct 3 ms 3908 KB Output is correct
48 Correct 3 ms 3820 KB Output is correct
49 Correct 3 ms 3820 KB Output is correct
50 Correct 3 ms 3820 KB Output is correct
51 Correct 4 ms 3820 KB Output is correct
52 Correct 3 ms 3820 KB Output is correct
53 Correct 3 ms 3820 KB Output is correct
54 Correct 3 ms 3820 KB Output is correct
55 Correct 3 ms 3884 KB Output is correct
56 Correct 3 ms 3820 KB Output is correct
57 Correct 3 ms 3820 KB Output is correct
58 Correct 3 ms 3820 KB Output is correct
59 Correct 3 ms 3820 KB Output is correct
60 Correct 4 ms 3820 KB Output is correct
61 Correct 4 ms 3820 KB Output is correct
62 Correct 4 ms 3820 KB Output is correct
63 Correct 3 ms 3820 KB Output is correct
64 Correct 3 ms 3820 KB Output is correct
65 Correct 4 ms 3820 KB Output is correct
66 Correct 3 ms 3820 KB Output is correct
67 Correct 3 ms 3820 KB Output is correct
68 Correct 29 ms 9964 KB Output is correct
69 Correct 54 ms 16128 KB Output is correct
70 Correct 4 ms 3820 KB Output is correct
71 Runtime error 64 ms 13804 KB Execution killed with signal 11
72 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3820 KB Output is correct
2 Correct 3 ms 3820 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 4 ms 3820 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 3 ms 3820 KB Output is correct
7 Correct 3 ms 3820 KB Output is correct
8 Correct 3 ms 3820 KB Output is correct
9 Correct 4 ms 3820 KB Output is correct
10 Correct 3 ms 3820 KB Output is correct
11 Correct 3 ms 3820 KB Output is correct
12 Correct 3 ms 3820 KB Output is correct
13 Correct 3 ms 3820 KB Output is correct
14 Correct 3 ms 3820 KB Output is correct
15 Correct 3 ms 3820 KB Output is correct
16 Correct 3 ms 3820 KB Output is correct
17 Correct 4 ms 3840 KB Output is correct
18 Correct 3 ms 3820 KB Output is correct
19 Correct 3 ms 3820 KB Output is correct
20 Correct 3 ms 3820 KB Output is correct
21 Correct 3 ms 3820 KB Output is correct
22 Correct 3 ms 3820 KB Output is correct
23 Correct 3 ms 3908 KB Output is correct
24 Correct 3 ms 3820 KB Output is correct
25 Correct 3 ms 3820 KB Output is correct
26 Correct 3 ms 3948 KB Output is correct
27 Correct 3 ms 3948 KB Output is correct
28 Correct 3 ms 3948 KB Output is correct
29 Correct 4 ms 3948 KB Output is correct
30 Correct 3 ms 3948 KB Output is correct
31 Correct 3 ms 3948 KB Output is correct
32 Correct 3 ms 3948 KB Output is correct
33 Correct 4 ms 3948 KB Output is correct
34 Correct 3 ms 3820 KB Output is correct
35 Correct 3 ms 3948 KB Output is correct
36 Correct 4 ms 3948 KB Output is correct
37 Correct 4 ms 3948 KB Output is correct
38 Correct 5 ms 3948 KB Output is correct
39 Correct 4 ms 3948 KB Output is correct
40 Correct 4 ms 3948 KB Output is correct
41 Correct 4 ms 3948 KB Output is correct
42 Correct 4 ms 3948 KB Output is correct
43 Correct 4 ms 3820 KB Output is correct
44 Correct 3 ms 3820 KB Output is correct
45 Correct 3 ms 3820 KB Output is correct
46 Correct 4 ms 3820 KB Output is correct
47 Correct 3 ms 3908 KB Output is correct
48 Correct 4 ms 3820 KB Output is correct
49 Correct 4 ms 3820 KB Output is correct
50 Correct 3 ms 3820 KB Output is correct
51 Correct 3 ms 3820 KB Output is correct
52 Correct 3 ms 3820 KB Output is correct
53 Correct 3 ms 3820 KB Output is correct
54 Correct 4 ms 3820 KB Output is correct
55 Correct 4 ms 3820 KB Output is correct
56 Correct 4 ms 3820 KB Output is correct
57 Correct 3 ms 3820 KB Output is correct
58 Correct 3 ms 3908 KB Output is correct
59 Correct 3 ms 3820 KB Output is correct
60 Correct 4 ms 3820 KB Output is correct
61 Correct 3 ms 3820 KB Output is correct
62 Correct 3 ms 3820 KB Output is correct
63 Correct 3 ms 3820 KB Output is correct
64 Correct 4 ms 3820 KB Output is correct
65 Correct 3 ms 3820 KB Output is correct
66 Correct 3 ms 3820 KB Output is correct
67 Correct 3 ms 3820 KB Output is correct
68 Correct 3 ms 3820 KB Output is correct
69 Correct 3 ms 3820 KB Output is correct
70 Correct 4 ms 3820 KB Output is correct
71 Correct 3 ms 3820 KB Output is correct
72 Correct 3 ms 3820 KB Output is correct
73 Correct 3 ms 3820 KB Output is correct
74 Correct 3 ms 3820 KB Output is correct
75 Correct 3 ms 3820 KB Output is correct
76 Correct 3 ms 3820 KB Output is correct
77 Correct 3 ms 3820 KB Output is correct
78 Correct 3 ms 3948 KB Output is correct
79 Correct 4 ms 3820 KB Output is correct
80 Correct 4 ms 3948 KB Output is correct
81 Correct 4 ms 3820 KB Output is correct
82 Correct 4 ms 3948 KB Output is correct
83 Correct 5 ms 3948 KB Output is correct
84 Correct 4 ms 3948 KB Output is correct
85 Correct 4 ms 3948 KB Output is correct
86 Correct 4 ms 3948 KB Output is correct
87 Correct 4 ms 3948 KB Output is correct
88 Correct 4 ms 3948 KB Output is correct
89 Correct 5 ms 3948 KB Output is correct
90 Correct 4 ms 3948 KB Output is correct
91 Correct 4 ms 3948 KB Output is correct
92 Correct 3 ms 3820 KB Output is correct
93 Correct 4 ms 3948 KB Output is correct
94 Correct 3 ms 3948 KB Output is correct
95 Correct 4 ms 3948 KB Output is correct
96 Correct 4 ms 3820 KB Output is correct
97 Correct 3 ms 3828 KB Output is correct
98 Correct 3 ms 3820 KB Output is correct
99 Correct 3 ms 3820 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3820 KB Output is correct
2 Correct 3 ms 3820 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 4 ms 3820 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 3 ms 3820 KB Output is correct
7 Correct 3 ms 3820 KB Output is correct
8 Correct 3 ms 3820 KB Output is correct
9 Correct 4 ms 3820 KB Output is correct
10 Correct 3 ms 3820 KB Output is correct
11 Correct 3 ms 3820 KB Output is correct
12 Correct 3 ms 3820 KB Output is correct
13 Correct 3 ms 3820 KB Output is correct
14 Correct 3 ms 3820 KB Output is correct
15 Correct 3 ms 3820 KB Output is correct
16 Correct 3 ms 3820 KB Output is correct
17 Correct 4 ms 3840 KB Output is correct
18 Correct 3 ms 3820 KB Output is correct
19 Correct 3 ms 3820 KB Output is correct
20 Correct 3 ms 3820 KB Output is correct
21 Correct 3 ms 3820 KB Output is correct
22 Correct 3 ms 3820 KB Output is correct
23 Correct 3 ms 3908 KB Output is correct
24 Correct 3 ms 3820 KB Output is correct
25 Correct 3 ms 3820 KB Output is correct
26 Correct 3 ms 3948 KB Output is correct
27 Correct 3 ms 3948 KB Output is correct
28 Correct 3 ms 3948 KB Output is correct
29 Correct 4 ms 3948 KB Output is correct
30 Correct 3 ms 3948 KB Output is correct
31 Correct 3 ms 3948 KB Output is correct
32 Correct 3 ms 3948 KB Output is correct
33 Correct 4 ms 3948 KB Output is correct
34 Correct 3 ms 3820 KB Output is correct
35 Correct 3 ms 3948 KB Output is correct
36 Correct 4 ms 3948 KB Output is correct
37 Correct 4 ms 3948 KB Output is correct
38 Correct 5 ms 3948 KB Output is correct
39 Correct 4 ms 3948 KB Output is correct
40 Correct 4 ms 3948 KB Output is correct
41 Correct 4 ms 3948 KB Output is correct
42 Correct 4 ms 3948 KB Output is correct
43 Correct 4 ms 3820 KB Output is correct
44 Correct 3 ms 3820 KB Output is correct
45 Correct 3 ms 3820 KB Output is correct
46 Correct 4 ms 3820 KB Output is correct
47 Correct 3 ms 3908 KB Output is correct
48 Correct 3 ms 3820 KB Output is correct
49 Correct 3 ms 3820 KB Output is correct
50 Correct 3 ms 3820 KB Output is correct
51 Correct 4 ms 3820 KB Output is correct
52 Correct 3 ms 3820 KB Output is correct
53 Correct 3 ms 3820 KB Output is correct
54 Correct 3 ms 3820 KB Output is correct
55 Correct 3 ms 3884 KB Output is correct
56 Correct 3 ms 3820 KB Output is correct
57 Correct 3 ms 3820 KB Output is correct
58 Correct 3 ms 3820 KB Output is correct
59 Correct 3 ms 3820 KB Output is correct
60 Correct 4 ms 3820 KB Output is correct
61 Correct 4 ms 3820 KB Output is correct
62 Correct 4 ms 3820 KB Output is correct
63 Correct 3 ms 3820 KB Output is correct
64 Correct 3 ms 3820 KB Output is correct
65 Correct 4 ms 3820 KB Output is correct
66 Correct 3 ms 3820 KB Output is correct
67 Correct 3 ms 3820 KB Output is correct
68 Correct 29 ms 9964 KB Output is correct
69 Correct 54 ms 16128 KB Output is correct
70 Correct 4 ms 3820 KB Output is correct
71 Runtime error 64 ms 13804 KB Execution killed with signal 11
72 Halted 0 ms 0 KB -