Submission #425452

#	Time	Username	Problem	Language	Result	Execution time	Memory
425452		errorgorn	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	578 ms	13752 KiB

roadsideadverts

#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 (stderr)

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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30