oj.uz

Submission #296823

# Submission time Handle Problem Language Result Execution time Memory
296823 2020-09-10T23:18:00 Z fivefourthreeone City Mapping (NOI18_citymapping) C++17
41 / 100
 19 ms 8448 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;
            int 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 18 ms 8448 KB Correct: 2990 out of 500000 queries used.
2 Correct 12 ms 8320 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 8320 KB Correct: 5750 out of 500000 queries used.
5 Correct 12 ms 8448 KB Correct: 4597 out of 500000 queries used.

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8448 KB Correct: 2990 out of 500000 queries used.
2 Correct 12 ms 8320 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 8320 KB Correct: 5750 out of 500000 queries used.
5 Correct 12 ms 8448 KB Correct: 4597 out of 500000 queries used.
6 Correct 14 ms 8448 KB Correct: 3259 out of 500000 queries used.
7 Correct 15 ms 8448 KB Correct: 2988 out of 500000 queries used.
8 Incorrect 4 ms 4608 KB get_distance() arguments out of range.
9 Halted 0 ms 0 KB -

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 19 ms 8440 KB Correct: 2972 out of 12000 queries used.
5 Correct 19 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 19 ms 8440 KB Correct: 2972 out of 12000 queries used.
5 Correct 19 ms 8320 KB Correct: 2966 out of 12000 queries used.
6 Correct 15 ms 8320 KB Correct: 3272 out of 12000 queries used.
7 Correct 17 ms 8320 KB Correct: 3107 out of 12000 queries used.
8 Correct 15 ms 8448 KB Correct: 3584 out of 12000 queries used.
9 Correct 15 ms 8448 KB Correct: 3583 out of 12000 queries used.
10 Correct 14 ms 8320 KB Correct: 3358 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8448 KB Correct: 2990 out of 500000 queries used.
2 Correct 12 ms 8320 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 8320 KB Correct: 5750 out of 500000 queries used.
5 Correct 12 ms 8448 KB Correct: 4597 out of 500000 queries used.
6 Correct 14 ms 8448 KB Correct: 3259 out of 500000 queries used.
7 Correct 15 ms 8448 KB Correct: 2988 out of 500000 queries used.
8 Incorrect 4 ms 4608 KB get_distance() arguments out of range.
9 Halted 0 ms 0 KB -