oj.uz

Submission #964004

# Submission time Handle Problem Language Result Execution time Memory
964004 2024-04-16T07:38:38 Z 12345678 City Mapping (NOI18_citymapping) C++17
22 / 100
 2000 ms 1116 KB 
#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e3+5;

ll ds[nx];
int hv[nx], l[nx], sz[nx], rt, pa[nx], w[nx], t;
vector<pair<int, int>> k;
vector<int> d[nx];
map<pair<int, int>, int> mp;

int dfssz(int u)
{
    sz[u]=1;
    for (auto v:d[u]) sz[u]+=dfssz(v);
    if (d[u].size()==1) hv[u]=d[u][0], l[u]=-1;
    else if (d[u].size()==2)
    {
        if (sz[d[u][0]]<sz[d[u][1]]) swap(d[u][0], d[u][1]);
        hv[u]=d[u][0];
        l[u]=d[u][1];
    }  
    return sz[u];
}

ll query(int u, int v)
{
    if (u>v) swap(u, v);
    if (mp.find({u, v})!=mp.end()) return mp[{u, v}];
    return mp[{u, v}]=get_distance(u, v);
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
    pair<int, int> mx;
    for (int i=2; i<=N; i++) mx=max(mx, {query(1, i), i});
    rt=mx.second;
    for (int i=1; i<=N; i++) if (i!=rt) ds[i]=query(rt, i), k.push_back({ds[i], i});
    sort(k.begin(), k.end());
    for (auto [_, u]:k)
    {
        //printf("here %d %d\n", rt, u);
        for (int i=1; i<=N; i++) hv[i]=l[i]=-1;
        dfssz(rt);
        int tmp=rt;
        while (1)
        {
            while (hv[tmp]!=-1) tmp=hv[tmp];
            //printf("here2 %d %d\n", u, tmp);
            ll x=query(u, tmp);
            ll ld=query(rt, tmp)-((query(rt, tmp)+query(rt, u))-query(u, tmp))/2;
            while (ld!=0) ld-=w[tmp], tmp=pa[tmp];
            if (d[tmp].size()<2) 
            {
                d[tmp].push_back(u), pa[u]=tmp, w[u]=query(u, tmp), A[t]=u, B[t]=tmp, W[t++]=query(u, tmp);
                break;
            }
            else tmp=l[tmp];
        } 
    }
}

Compilation message

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:53:16: warning: unused variable 'x' [-Wunused-variable]
   53 |             ll x=query(u, tmp);
      |                ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Correct: 2991 out of 500000 queries used.
2 Correct 7 ms 860 KB Correct: 3737 out of 500000 queries used.
3 Correct 9 ms 1108 KB Correct: 5893 out of 500000 queries used.
4 Correct 9 ms 1116 KB Correct: 7100 out of 500000 queries used.
5 Correct 9 ms 860 KB Correct: 3924 out of 500000 queries used.

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Correct: 2991 out of 500000 queries used.
2 Correct 7 ms 860 KB Correct: 3737 out of 500000 queries used.
3 Correct 9 ms 1108 KB Correct: 5893 out of 500000 queries used.
4 Correct 9 ms 1116 KB Correct: 7100 out of 500000 queries used.
5 Correct 9 ms 860 KB Correct: 3924 out of 500000 queries used.
6 Execution timed out 2021 ms 600 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Correct: 2967 out of 12000 queries used.
2 Correct 8 ms 880 KB Correct: 2973 out of 12000 queries used.
3 Correct 8 ms 860 KB Correct: 2994 out of 12000 queries used.
4 Correct 8 ms 860 KB Correct: 2973 out of 12000 queries used.
5 Correct 8 ms 860 KB Correct: 2967 out of 12000 queries used.

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Correct: 2967 out of 12000 queries used.
2 Correct 8 ms 880 KB Correct: 2973 out of 12000 queries used.
3 Correct 8 ms 860 KB Correct: 2994 out of 12000 queries used.
4 Correct 8 ms 860 KB Correct: 2973 out of 12000 queries used.
5 Correct 8 ms 860 KB Correct: 2967 out of 12000 queries used.
6 Execution timed out 2062 ms 604 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Correct: 2991 out of 500000 queries used.
2 Correct 7 ms 860 KB Correct: 3737 out of 500000 queries used.
3 Correct 9 ms 1108 KB Correct: 5893 out of 500000 queries used.
4 Correct 9 ms 1116 KB Correct: 7100 out of 500000 queries used.
5 Correct 9 ms 860 KB Correct: 3924 out of 500000 queries used.
6 Execution timed out 2021 ms 600 KB Time limit exceeded
7 Halted 0 ms 0 KB -