Submission #473989

#	Time	Username	Problem	Language	Result	Execution time	Memory
473989		Blobo2_Blobo2	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	1093 ms	183388 KiB

merchant

/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int16_t
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty ios_base::sync_with_stdio(false);cin.tie(0);
#define EPS 0.00000001

const int mo=1e9+7,INF=1e18;
int nxt(){int x;cin>>x;return x;}
int n,m,k,val[101][1001][2];
vector<pair<int,int> > adj[101];
set<vector<int> >cycle;
int now =-1;
int vis[101];
vector<int> nodes;
void store(int u,int start){
    for(auto v:adj[u]){
        if(v.first == start){
            nodes.push_back(nodes[0]);
            cycle.insert(nodes);
            return;
        }
        if(vis[v.first] == vis[u]+1){
            nodes.push_back(v.first);
            store(v.first,start);
        }
    }
}
void dfs(int u,int par = -1){
    if(par == -1)vis[u]=1;
    else vis[u] = vis[par] + 1;
    for(auto v:adj[u]){
        if(!vis[v.first] && v.first > now)
            dfs(v.first,u);
        else{
            nodes.clear();
            nodes.push_back(v.first);
            store(v.first,v.first);
        }
    }
    vis[u] = 0;
}

int elmostoptimal(int idx = 0,int product = -1){
    //cout<<idx<<' '<<endl;
    if(idx == nodes.size())
        return 0;
    int ret = 0;
    if(product != -1)
        ret = max(ret,elmostoptimal(idx+1,-1) + val[nodes[idx]][product][1]);
    ret=max(ret, elmostoptimal(idx+1,product));
    for(int i=0;i<k;i++){
        if(val[nodes[idx]][i][0] != -1){
            if(product!=-1)
                ret= max(ret,elmostoptimal(idx+1,i) + (val[nodes[idx]][product][1]-val[nodes[idx]][i][0] ));
            else
                ret= max(ret,elmostoptimal(idx+1,i) - val[nodes[idx]][i][0]);
        }
    }
    return ret;
}
signed main(){
    Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
    n=nxt(),m=nxt(),k=nxt();
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            val[i][j][0] = nxt();
            val[i][j][1] = nxt();
        }
    }
    int distance[n][n];
    memset(distance,0,sizeof distance);
    for(int i=0;i<m;i++){
        int x=nxt()-1,y=nxt()-1,c=nxt();
        adj[x].push_back({y,c});
        distance[x][y] = c;
    }
    for(int i=0;i<n;i++){
        now = i;
        dfs(i);
        memset(vis,0,sizeof vis);
    }
    int mx = 0;
    int dis[cycle.size()];
    memset(dis,0,sizeof dis);
    int i=0;
    for(auto x:cycle){
        for(int j=0;j<n;j++){
            int u = x[j], v = x[(j+1)%n];
            dis[i] += distance[u][v];
        }
        i++;
    }
    i=0;
    for(auto x:cycle){
        nodes.clear();
        nodes = x;
        /*for(int j=0;j<nodes.size();j++)cout<<nodes[j]<<' ';
        cout<<endl;*/
        int ans = elmostoptimal();
        mx=max(mx,ans / dis[i]);
        //cout<<ans<<endl;
        i++;
    }
    cout<<mx;
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'long long int elmostoptimal(long long int, long long int)':
merchant.cpp:60:12: 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]
   60 |     if(idx == nodes.size())
      |        ~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34