oj.uz

Submission #425452

# Submission time Handle Problem Language Result Execution time Memory
425452 2021-06-13T03:59:41 Z errorgorn Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 578 ms 13752 KB 
#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;
typedef pair<int,int> ii;
ii p[50005][18];
vector<ii> al[50005];
int arr[5],memo[5][32];
void dfs(int i){
    int j;
    for (int x=0;x<al[i].size();x++){
        if (p[al[i][x].first][0]==ii(-1,-1) && al[i][x].first){
            p[al[i][x].first][0]=ii(i,al[i][x].second);
            j=i;
            for (int y=1;p[j][y-1]!=ii(-1,-1);y++){
                p[al[i][x].first][y]=ii(p[j][y-1].first,p[j][y-1].second+p[al[i][x].first][y-1].second);
                j=p[al[i][x].first][y].first;
            }
            dfs(al[i][x].first);
        }
    }
}
int dist(int i){
    int k=0;
    for (int x=17;x>=0;x--){
        if (p[i][x]!=ii(-1,-1)){
            k+=p[i][x].second;
            i=p[i][x].first;
        }
    }
    return k;
}
int level(int i){
    int k=0;
    for (int x=17;x>=0;x--){
        if (p[i][x]!=ii(-1,-1)){
            k+=(1<<x);
            i=p[i][x].first;
        }
    }
    return k;
}
int traverse(int i,int j){
    for (int x=17;x>=0;x--){
        if ((j&(1<<x))!=0){
            i=p[i][x].first;
        }
    }
    return i;
}
int lca(int i,int j){
    if (level(j)>level(i)) swap(i,j);
    i=traverse(i, level(i)-level(j));
    if (i==j) return i;
    for (int x=17;x>=0;x--){
        if (p[i][x]!=ii(-1,-1) && p[i][x].first!=p[j][x].first){
            i=p[i][x].first;
            j=p[j][x].first;
        }
    }
    return p[i][0].first;
}
int dist(int i,int j){
    return dist(i)+dist(j)-2*dist(lca(i,j));
}
int tsp(int i,int bitmask){
    if (memo[i][bitmask]!=-1) return memo[i][bitmask];
    if (bitmask==31) return memo[i][bitmask]=dist(arr[i],arr[0]);
    int ans=1000000000;
    for (int x=1;x<5;x++){
        if ((bitmask&(1<<x))==0){
            ans=min(ans,dist(arr[i],arr[x])+tsp(x,bitmask|(1<<x)));
        }
    }
    return memo[i][bitmask]=ans;
}
void print2(){
    for (int x=0;x<5;x++){
        for (int y=0;y<5;y++){
            printf("%d %d %d\n",x,y,dist(x,y));
        }
    }
}
int main(){
    int query,a,b,c;
    scanf("%d",&query);
    while (--query){
        scanf("%d%d%d",&a,&b,&c);
        al[a].push_back(ii (b,c));
        al[b].push_back(ii (a,c));
    }
    memset(p,-1,sizeof(p));
    dfs(0);
    scanf("%d",&query);
    while (query--){
        memset(memo,-1,sizeof(memo));
        for (int x=0;x<5;x++) scanf("%d",&arr[x]);
        printf("%d\n",tsp(0,1)>>1);
    }
}

Compilation message

roadsideadverts.cpp: In function 'void dfs(int)':
roadsideadverts.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int x=0;x<al[i].size();x++){
      |                  ~^~~~~~~~~~~~~
roadsideadverts.cpp: In function 'int main()':
roadsideadverts.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     scanf("%d",&query);
      |     ~~~~~^~~~~~~~~~~~~
roadsideadverts.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%d%d%d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%d",&query);
      |     ~~~~~^~~~~~~~~~~~~
roadsideadverts.cpp:98:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         for (int x=0;x<5;x++) scanf("%d",&arr[x]);
      |                               ~~~~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8396 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 12324 KB Output is correct
2 Correct 536 ms 13520 KB Output is correct
3 Correct 480 ms 13628 KB Output is correct
4 Correct 483 ms 13428 KB Output is correct
5 Correct 497 ms 13544 KB Output is correct
6 Correct 543 ms 13508 KB Output is correct
7 Correct 555 ms 13472 KB Output is correct
8 Correct 547 ms 13508 KB Output is correct
9 Correct 483 ms 13516 KB Output is correct
10 Correct 555 ms 13752 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11076 KB Output is correct
2 Correct 54 ms 12780 KB Output is correct
3 Correct 55 ms 12748 KB Output is correct
4 Correct 81 ms 12788 KB Output is correct
5 Correct 64 ms 12744 KB Output is correct
6 Correct 59 ms 12916 KB Output is correct
7 Correct 82 ms 12736 KB Output is correct
8 Correct 55 ms 12824 KB Output is correct
9 Correct 55 ms 12740 KB Output is correct
10 Correct 87 ms 12720 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8396 KB Output is correct
2 Correct 494 ms 12324 KB Output is correct
3 Correct 536 ms 13520 KB Output is correct
4 Correct 480 ms 13628 KB Output is correct
5 Correct 483 ms 13428 KB Output is correct
6 Correct 497 ms 13544 KB Output is correct
7 Correct 543 ms 13508 KB Output is correct
8 Correct 555 ms 13472 KB Output is correct
9 Correct 547 ms 13508 KB Output is correct
10 Correct 483 ms 13516 KB Output is correct
11 Correct 555 ms 13752 KB Output is correct
12 Correct 53 ms 11076 KB Output is correct
13 Correct 54 ms 12780 KB Output is correct
14 Correct 55 ms 12748 KB Output is correct
15 Correct 81 ms 12788 KB Output is correct
16 Correct 64 ms 12744 KB Output is correct
17 Correct 59 ms 12916 KB Output is correct
18 Correct 82 ms 12736 KB Output is correct
19 Correct 55 ms 12824 KB Output is correct
20 Correct 55 ms 12740 KB Output is correct
21 Correct 87 ms 12720 KB Output is correct
22 Correct 494 ms 12544 KB Output is correct
23 Correct 238 ms 11332 KB Output is correct
24 Correct 512 ms 13268 KB Output is correct
25 Correct 523 ms 13340 KB Output is correct
26 Correct 495 ms 13268 KB Output is correct
27 Correct 459 ms 13112 KB Output is correct
28 Correct 578 ms 13092 KB Output is correct
29 Correct 502 ms 13480 KB Output is correct
30 Correct 535 ms 13384 KB Output is correct
31 Correct 553 ms 13212 KB Output is correct