oj.uz

Submission #296827

# Submission time Handle Problem Language Result Execution time Memory
296827 2020-09-11T00:02:17 Z fivefourthreeone City Mapping (NOI18_citymapping) C++17
100 / 100
 19 ms 8480 KB 
    #include "citymapping.h"
            //#pragma GCC target ("avx2")
            #pragma GCC optimization ("O3")
            #pragma GCC optimization ("unroll-loops")
            #include <bits/stdc++.h>
            #define owo(i,a, b) for(auto i=(a);i<(b); ++i)
            #define uwu(i,a, b) for(auto i=(a)-1; i>=(b); --i)
            #define senpai push_back
            #define ttgl pair<int, int>
            #define ayaya cout<<"ayaya~"<<endl
            using namespace std;
            /*#include <ext/pb_ds/assoc_container.hpp>
            #include <ext/pb_ds/tree_policy.hpp>
            using namespace __gnu_pbds;
            #define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
             
            using ll = long long;
            using ld = long double;
            const ll MOD = 1000000007;
            const ll root = 62;
            ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
            ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
            ll modInv(ll a){return binpow(a, MOD-2);}
            const double PI = acos(-1);
            const double eps = 1e-6;
            const int INF = 0x3f3f3f3f;
            const int NINF = 0xc0c0c0c0;
            const ll INFLL = 0x3f3f3f3f3f3f3f3f;
            const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
            const int mxN = 1001;
            ll dist[mxN][mxN];
            int sz[mxN];
            int par[mxN];
            int rt;
            vector<pair<int, ll>> adj[mxN];
            //ll get_distance(int a, int b) {return 0;}
            ll qd(int a, int b) {
                if(a==b)return 0;
                if(dist[a][b])return dist[a][b];
                return dist[a][b] = dist[b][a] = get_distance(a, b);
            }
            int find(int u) {
                if(adj[u].size()==0)return u;
                int mx = 0;
                int cc = 0;
                for(auto v: adj[u]) {
                    if(sz[v.first] > mx) {
                        mx = sz[v.first];
                        cc = v.first;
                    }
                }
                return find(cc);
            }
            int solve(int u, int res, ll w) {
                if(adj[u].size()==0)return u;
                int bot = find(u);
                int nxt = bot;
              	int bdd = nxt;
                ll path = qd(res, nxt);
                while(qd(u, bot) + w  < qd(u, nxt)*2 + path) {
                  	bdd = nxt;
                    nxt = par[nxt];
                }
                if(adj[nxt].size()<=1)return nxt;
              	if(adj[nxt][0].first==bdd)swap(adj[nxt][0], adj[nxt][1]);
                return solve(adj[nxt][0].first, res, w - qd(u, adj[nxt][0].first));
            }
            int n;
            void find_roads(int N, int Q, int* a, int* b, int* w) {
                n = N;
                ll mxd = 0;
                owo(i, 1, n+1) {
                    if(qd(i, 1) > mxd) {
                        mxd = qd(i, 1);
                        rt = i;
                    }
                }
                sz[rt] = 1;
                vector<pair<ll, int>> all;
                owo(i, 1, n+1) {
                    if(i^rt) {
                        all.senpai({qd(i, rt), i});
                    }
                }
                sort(all.begin(), all.end());
                for(auto p: all) {
                    par[p.second] = solve(rt, p.second, p.first);
                    adj[par[p.second]].senpai({p.second, p.first - qd(par[p.second], rt)});
                    int up = p.second;
                    while(up) {
                        sz[p.second]++;
                        dist[up][p.second] = dist[p.second][up] = qd(rt, p.second) - qd(rt, up);
                        up = par[up];
                    }
                }
                int cnt = 0;
                owo(i, 1, n+1) {
                    for(auto p: adj[i]) {
                        a[cnt] = i;
                        b[cnt] = p.first;
                        w[cnt++] = p.second;
                    }
                }
            }
            /*int main() {
                //freopen("file.in", "r", stdin);
                //freopen("file.out", "w", stdout);
                mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
                cin.tie(0)->sync_with_stdio(0);
                return 0;
            }*/

Compilation message

citymapping.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 |             #pragma GCC optimization ("O3")
      | 
citymapping.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 |             #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8312 KB Correct: 2990 out of 500000 queries used.
2 Correct 12 ms 8448 KB Correct: 2992 out of 500000 queries used.
3 Correct 9 ms 8320 KB Correct: 5386 out of 500000 queries used.
4 Correct 8 ms 8352 KB Correct: 5750 out of 500000 queries used.
5 Correct 10 ms 8448 KB Correct: 4597 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8312 KB Correct: 2990 out of 500000 queries used.
2 Correct 12 ms 8448 KB Correct: 2992 out of 500000 queries used.
3 Correct 9 ms 8320 KB Correct: 5386 out of 500000 queries used.
4 Correct 8 ms 8352 KB Correct: 5750 out of 500000 queries used.
5 Correct 10 ms 8448 KB Correct: 4597 out of 500000 queries used.
6 Correct 19 ms 8320 KB Correct: 2981 out of 500000 queries used.
7 Correct 14 ms 8448 KB Correct: 2988 out of 500000 queries used.
8 Correct 9 ms 8320 KB Correct: 5245 out of 500000 queries used.
9 Correct 9 ms 8320 KB Correct: 5569 out of 500000 queries used.
10 Correct 10 ms 8320 KB Correct: 4509 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8320 KB Correct: 2966 out of 12000 queries used.
2 Correct 18 ms 8320 KB Correct: 2972 out of 12000 queries used.
3 Correct 18 ms 8448 KB Correct: 2993 out of 12000 queries used.
4 Correct 18 ms 8320 KB Correct: 2972 out of 12000 queries used.
5 Correct 18 ms 8320 KB Correct: 2966 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8320 KB Correct: 2966 out of 12000 queries used.
2 Correct 18 ms 8320 KB Correct: 2972 out of 12000 queries used.
3 Correct 18 ms 8448 KB Correct: 2993 out of 12000 queries used.
4 Correct 18 ms 8320 KB Correct: 2972 out of 12000 queries used.
5 Correct 18 ms 8320 KB Correct: 2966 out of 12000 queries used.
6 Correct 18 ms 8320 KB Correct: 2987 out of 12000 queries used.
7 Correct 18 ms 8320 KB Correct: 2981 out of 12000 queries used.
8 Correct 19 ms 8448 KB Correct: 2993 out of 12000 queries used.
9 Correct 18 ms 8320 KB Correct: 2984 out of 12000 queries used.
10 Correct 19 ms 8448 KB Correct: 2975 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8312 KB Correct: 2990 out of 500000 queries used.
2 Correct 12 ms 8448 KB Correct: 2992 out of 500000 queries used.
3 Correct 9 ms 8320 KB Correct: 5386 out of 500000 queries used.
4 Correct 8 ms 8352 KB Correct: 5750 out of 500000 queries used.
5 Correct 10 ms 8448 KB Correct: 4597 out of 500000 queries used.
6 Correct 19 ms 8320 KB Correct: 2981 out of 500000 queries used.
7 Correct 14 ms 8448 KB Correct: 2988 out of 500000 queries used.
8 Correct 9 ms 8320 KB Correct: 5245 out of 500000 queries used.
9 Correct 9 ms 8320 KB Correct: 5569 out of 500000 queries used.
10 Correct 10 ms 8320 KB Correct: 4509 out of 500000 queries used.
11 Correct 18 ms 8320 KB Correct: 2966 out of 12000 queries used.
12 Correct 18 ms 8320 KB Correct: 2972 out of 12000 queries used.
13 Correct 18 ms 8448 KB Correct: 2993 out of 12000 queries used.
14 Correct 18 ms 8320 KB Correct: 2972 out of 12000 queries used.
15 Correct 18 ms 8320 KB Correct: 2966 out of 12000 queries used.
16 Correct 18 ms 8320 KB Correct: 2987 out of 12000 queries used.
17 Correct 18 ms 8320 KB Correct: 2981 out of 12000 queries used.
18 Correct 19 ms 8448 KB Correct: 2993 out of 12000 queries used.
19 Correct 18 ms 8320 KB Correct: 2984 out of 12000 queries used.
20 Correct 19 ms 8448 KB Correct: 2975 out of 12000 queries used.
21 Correct 18 ms 8320 KB Correct: 2981 out of 25000 queries used.
22 Correct 14 ms 8448 KB Correct: 2990 out of 25000 queries used.
23 Correct 15 ms 8448 KB Correct: 2972 out of 25000 queries used.
24 Correct 15 ms 8320 KB Correct: 2969 out of 25000 queries used.
25 Correct 9 ms 8320 KB Correct: 5197 out of 25000 queries used.
26 Correct 9 ms 8320 KB Correct: 5048 out of 25000 queries used.
27 Correct 9 ms 8320 KB Correct: 5115 out of 25000 queries used.
28 Correct 9 ms 8320 KB Correct: 5288 out of 25000 queries used.
29 Correct 9 ms 8448 KB Correct: 5288 out of 25000 queries used.
30 Correct 9 ms 8320 KB Correct: 5361 out of 25000 queries used.
31 Correct 9 ms 8448 KB Correct: 5446 out of 25000 queries used.
32 Correct 18 ms 8448 KB Correct: 2978 out of 25000 queries used.
33 Correct 9 ms 8320 KB Correct: 5218 out of 25000 queries used.
34 Correct 9 ms 8480 KB Correct: 5476 out of 25000 queries used.
35 Correct 9 ms 8320 KB Correct: 5358 out of 25000 queries used.
36 Correct 9 ms 8320 KB Correct: 5424 out of 25000 queries used.
37 Correct 9 ms 8320 KB Correct: 5515 out of 25000 queries used.
38 Correct 9 ms 8448 KB Correct: 5393 out of 25000 queries used.
39 Correct 9 ms 8320 KB Correct: 5446 out of 25000 queries used.
40 Correct 9 ms 8320 KB Correct: 5500 out of 25000 queries used.
41 Correct 9 ms 8448 KB Correct: 5499 out of 25000 queries used.
42 Correct 8 ms 8320 KB Correct: 5329 out of 25000 queries used.
43 Correct 18 ms 8448 KB Correct: 2987 out of 25000 queries used.
44 Correct 9 ms 8320 KB Correct: 5289 out of 25000 queries used.
45 Correct 8 ms 8320 KB Correct: 5380 out of 25000 queries used.
46 Correct 8 ms 8320 KB Correct: 5360 out of 25000 queries used.
47 Correct 8 ms 8320 KB Correct: 5430 out of 25000 queries used.
48 Correct 8 ms 8448 KB Correct: 5404 out of 25000 queries used.
49 Correct 9 ms 8320 KB Correct: 5446 out of 25000 queries used.
50 Correct 8 ms 8320 KB Correct: 5255 out of 25000 queries used.
51 Correct 8 ms 8320 KB Correct: 5443 out of 25000 queries used.
52 Correct 9 ms 8448 KB Correct: 5407 out of 25000 queries used.
53 Correct 8 ms 8448 KB Correct: 5459 out of 25000 queries used.
54 Correct 14 ms 8448 KB Correct: 2993 out of 25000 queries used.
55 Correct 8 ms 8448 KB Correct: 5453 out of 25000 queries used.
56 Correct 9 ms 8320 KB Correct: 5534 out of 25000 queries used.
57 Correct 9 ms 8320 KB Correct: 5529 out of 25000 queries used.
58 Correct 8 ms 8320 KB Correct: 5388 out of 25000 queries used.
59 Correct 8 ms 8320 KB Correct: 5347 out of 25000 queries used.
60 Correct 10 ms 8320 KB Correct: 4456 out of 25000 queries used.
61 Correct 10 ms 8352 KB Correct: 4568 out of 25000 queries used.
62 Correct 10 ms 8320 KB Correct: 4557 out of 25000 queries used.
63 Correct 11 ms 8320 KB Correct: 4474 out of 25000 queries used.
64 Correct 10 ms 8320 KB Correct: 4522 out of 25000 queries used.
65 Correct 14 ms 8320 KB Correct: 2966 out of 25000 queries used.
66 Correct 10 ms 8320 KB Correct: 4527 out of 25000 queries used.
67 Correct 15 ms 8320 KB Correct: 2939 out of 25000 queries used.
68 Correct 15 ms 8320 KB Correct: 2969 out of 25000 queries used.
69 Correct 15 ms 8320 KB Correct: 2985 out of 25000 queries used.
70 Correct 16 ms 8448 KB Correct: 2976 out of 25000 queries used.