Submission #1115629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115629		EfeBabagil	Trains (BOI24_trains)	C++14	21 / 100	1250 ms	1048576 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int mod=1e9+7;
 
vector<int> arr[N];
 
int vis[N];
stack<int> st;
/*void dfs(int x)
{
    vis[x]=1;
    for(int i=0;i<arr[x].size();i++)
    {
        if(!vis[i])
        dfs(i);
    }
    st.push(x);
}
*/
int32_t main()
{
    
    int n;
    cin>>n;
    vector<pair<int,int>> city(n);
    vector<int> ans(n);
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        city[i]={a,b};
    }
    for(int i=0;i<n;i++)
    {
        int d=city[i].first;
        int x=city[i].second;
        if(d==0)
        continue;
        for(int t=1;t<=x;t++)
        {
            if(i+t*d>=n)
            break;
            arr[i].push_back(i+t*d);
        }
    }
    /*for(int i=0;i<arr[0].size();i++)
    cout<<arr[0][i]<<" ";
    cout<<endl;*/
    /*
    for(int i=0;i<n;i++)
    {
        if(!vis[i])
        dfs(i);
    }
    vector<int> topo;
    while(!st.empty())
    {
        topo.push_back(st.top());
        //cout<<st.top()<<" ";
        st.pop();
    }*/
    ans[0]=1;
    for(int j=0;j<n;j++)
    {
        int x=j;
        for(int i=0;i<arr[x].size();i++)
        {
            ans[arr[x][i]]=(ans[arr[x][i]]+ans[x])%mod;
        }
    }
    int tot=0;
    //cout<<endl;
    for(int i=0;i<n;i++)
    {
        //cout<<ans[i]<<" ";
        tot=(tot+ans[i])%mod;
    }
    cout<<tot;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:68:22: 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]
   68 |         for(int i=0;i<arr[x].size();i++)
      |                     ~^~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29