Submission #474097

#	Time	Username	Problem	Language	Result	Execution time	Memory
474097		ShahdMohamed	Paths (BOI18_paths)	C++17	100 / 100	907 ms	116948 KiB

paths

///LW M4 ACC HAZ3L GAMED
///YARAB WALA...I MEAN YARAB ACC
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
const ll mod = (ll) 1e9 + 7;
using namespace std;
ll n,m,k;
vector<ll>c;
vector<string>s;
vector<vector<ll>>v(300001);
vector<vector<ll>>dp(300001,vector<ll>(34,-1));
void yap()
{
    s.push_back("0");
    s.push_back("1");
    s.push_back("2");
    s.push_back("3");
    s.push_back("4");
    s.push_back("5");
    s.push_back("12");
    s.push_back("13");
    s.push_back("14");
    s.push_back("15");
    s.push_back("23");
    s.push_back("24");
    s.push_back("25");
    s.push_back("34");
    s.push_back("35");
    s.push_back("45");
    s.push_back("123");
    s.push_back("124");
    s.push_back("125");
    s.push_back("134");
    s.push_back("135");
    s.push_back("145");
    s.push_back("234");
    s.push_back("235");
    s.push_back("245");
    s.push_back("345");
    s.push_back("1234");
    s.push_back("1235");
    s.push_back("1245");
    s.push_back("1345");
    s.push_back("2345");
    s.push_back("12345");
}
ll num(string st)
{
    for (ll i=1; i<=31; i++)
    {
        if (s[i]==st)
            return i;
    }
}
ll solve(ll node,ll nm)
{
    string st=s[nm];
    if (dp[node][nm]!=-1)
        return dp[node][nm];
    ll ans=1;
    for (auto ch:v[node])
    {
        string f=to_string(c[ch]);
        ll a=st.find(f[0]);
        if (a<0 or a>=st.size())
        {
            string fans=st;
            fans+=f;
            sort(fans.begin(),fans.end());
            ll g=num(fans);
            ans+=solve(ch,g);
        }
    }
    return dp[node][nm]=ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    yap();
    cin>>n>>m>>k;
    c.resize(n+1);
    for (ll i=1; i<=n; i++)
    {
        cin>>c[i];
    }
    for (ll i=0; i<m; i++)
    {
        ll a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    ll sum=0;
    for (ll i=1; i<=n; i++)
    {
        string f=to_string(c[i]);
        ll g=num(f);
        sum+=solve(i,g);
        sum--;
    }
    cout<<sum<<endl;

    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'long long int solve(long long int, long long int)':
paths.cpp:66:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if (a<0 or a>=st.size())
      |                    ~^~~~~~~~~~~
paths.cpp: In function 'long long int num(std::string)':
paths.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
   55 | }
      | ^

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30