oj.uz

Submission #941689

# Submission time Handle Problem Language Result Execution time Memory
941689 2024-03-09T09:47:38 Z abcvuitunggio City Mapping (NOI18_citymapping) C++17
32 / 100
 2000 ms 5724 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
    int a,b,w;
};
int d[1001][1001],h[1001],deg[1001];
vector <edge> res;
vector <pair <int, int>> tmp;
vector <int> ve[1001];
vector <pair <int, int>> ke[1001];
map <int, int> mp;
int get(int i, int j){
    if (i==j)
        return 0;
    if (i>j)
        swap(i,j);
    if (d[i][j])
        return d[i][j];
    return d[i][j]=get_distance(i,j);
}
void addEdge(int a, int b, int w){
    deg[a]++;
    deg[b]++;
    res.push_back({a,b,w});
}
void dfs(int u, int p, int root, int cur=0){
    d[root][u]=d[u][root]=cur;
    for (auto [v,w]:ke[u])
        if (v!=p)
            dfs(v,u,root,cur+w);
}
void solve(int x){
    sort(ve[x].begin(),ve[x].end(),[](int i, int j){return h[i]<h[j];});
    addEdge(x,ve[x][0],h[ve[x][0]]);
    for (int i=1;i<ve[x].size();i++){
        vector <pair <int, int>> c;
        int u=ve[x][i];
        for (int j=0;j<i;j++)
            if (deg[ve[x][j]]<3)
                c.push_back({ve[x][j],h[u]-h[ve[x][j]]});
        while (c.size()>1){
            int val=get(c[0].first,u);
            vector <pair <int, int>> c2;
            for (auto [i,j]:c)
                if (get(c[0].first,i)+j==val)
                    c2.push_back({i,j});
            swap(c,c2);
        }
        auto [v,w]=c[0];
        addEdge(u,v,w);
        ke[u].push_back({v,w});
        ke[v].push_back({u,w});
        dfs(u,u,u);
    }
}
void find_roads(int32_t n, int32_t Q, int32_t A[], int32_t B[], int32_t W[]){
    int a=1,b=1,mx=0;
    for (int i=2;i<=n;i++)
        if (mx<get(1,i)){
            a=i;
            mx=get(1,i);
        }
    mx=0;
    for (int i=1;i<=n;i++)
        if (mx<get(a,i)){
            b=i;
            mx=get(a,i);
        }
    for (int i=1;i<=n;i++)
        if (get(a,i)+get(i,b)==get(a,b)){
            tmp.push_back({get(a,i),i});
            mp[get(a,i)]=i;
        }
    sort(tmp.begin(),tmp.end());
    for (int i=0;i+1<tmp.size();i++)
        addEdge(tmp[i].second,tmp[i+1].second,tmp[i+1].first-tmp[i].first);
    for (int i=1;i<=n;i++){
        int da=(get(a,b)+get(a,i)-get(b,i))/2;
        h[i]=(get(a,i)+get(b,i)-get(a,b))/2;
        if (mp[da]!=i)
            ve[mp[da]].push_back(i);
    }
    for (int i=1;i<=n;i++)
        if (!ve[i].empty())
            solve(i);
    for (int i=0;i<n-1;i++){
        A[i]=res[i].a;
        B[i]=res[i].b;
        W[i]=res[i].w;
    }
}

Compilation message

citymapping.cpp: In function 'void solve(long long int)':
citymapping.cpp:37:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=1;i<ve[x].size();i++){
      |                  ~^~~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int32_t, int32_t, int32_t*, int32_t*, int32_t*)':
citymapping.cpp:77:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i=0;i+1<tmp.size();i++)
      |                  ~~~^~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2908 KB Correct: 2991 out of 500000 queries used.
2 Correct 2 ms 1884 KB Correct: 2994 out of 500000 queries used.
3 Execution timed out 2024 ms 1628 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2908 KB Correct: 2991 out of 500000 queries used.
2 Correct 2 ms 1884 KB Correct: 2994 out of 500000 queries used.
3 Execution timed out 2024 ms 1628 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Correct: 2967 out of 12000 queries used.
2 Correct 2 ms 1880 KB Correct: 2973 out of 12000 queries used.
3 Correct 3 ms 3932 KB Correct: 2994 out of 12000 queries used.
4 Correct 2 ms 2392 KB Correct: 2973 out of 12000 queries used.
5 Correct 3 ms 4952 KB Correct: 2967 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Correct: 2967 out of 12000 queries used.
2 Correct 2 ms 1880 KB Correct: 2973 out of 12000 queries used.
3 Correct 3 ms 3932 KB Correct: 2994 out of 12000 queries used.
4 Correct 2 ms 2392 KB Correct: 2973 out of 12000 queries used.
5 Correct 3 ms 4952 KB Correct: 2967 out of 12000 queries used.
6 Correct 2 ms 3416 KB Correct: 2988 out of 12000 queries used.
7 Correct 3 ms 4700 KB Correct: 2982 out of 12000 queries used.
8 Correct 3 ms 5724 KB Correct: 2994 out of 12000 queries used.
9 Correct 3 ms 3676 KB Correct: 2985 out of 12000 queries used.
10 Correct 3 ms 3676 KB Correct: 2976 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2908 KB Correct: 2991 out of 500000 queries used.
2 Correct 2 ms 1884 KB Correct: 2994 out of 500000 queries used.
3 Execution timed out 2024 ms 1628 KB Time limit exceeded
4 Halted 0 ms 0 KB -