oj.uz

Submission #363231

# Submission time Handle Problem Language Result Execution time Memory
363231 2021-02-05T10:16:16 Z Tenis0206 Shell (info1cup18_shell) C++11
100 / 100
 592 ms 81512 KB 
#include <bits/stdc++.h>

using namespace std;
const int Mod = 1e9+7;
int n,m,p,spc[1000005];
long long lvl[1000005],cnt[1000005];
bool sel[1000005];
vector<int> G[1000005],IN[1000005],d;
void dfs(int x)
{
    sel[x]=true;
    for(auto it : G[x])
    {
        if(!sel[it])
        {
            dfs(it);
        }
    }
    d.push_back(x);
}
void topsort()
{
    dfs(1);
    reverse(d.begin(),d.end());
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>p;
    for(int i=1;i<=p;i++)
    {
        int x;
        cin>>x;
        spc[x]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        IN[y].push_back(x);
    }
    topsort();
    memset(sel,false,sizeof(sel));
    cnt[1]=1;
    for(auto nod : d)
    {
        sel[nod]=true;
        int tofind = 0;
        if(spc[nod])
        {
            lvl[nod]=spc[nod];
        }
        for(auto it : IN[nod])
        {
            if(!spc[nod] && lvl[it]>lvl[nod])
            {
                lvl[nod]=lvl[it];
                cnt[nod]=0;
            }
            if(!spc[nod] && lvl[it]==lvl[nod])
            {
                cnt[nod]+=cnt[it];
                cnt[nod]%=Mod;
            }
            if(spc[nod] && lvl[it]==lvl[nod]-1)
            {
                cnt[nod]+=cnt[it];
                cnt[nod]%=Mod;
            }
        }
    }
    if(lvl[n]==p)
    {
        cout<<cnt[n]%Mod<<'\n';
        return 0;
    }
    cout<<0<<'\n';
    return 0;
}

Compilation message

shell.cpp: In function 'int main()':
shell.cpp:50:13: warning: unused variable 'tofind' [-Wunused-variable]
   50 |         int tofind = 0;
      |             ^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 48364 KB Output is correct
2 Correct 33 ms 48364 KB Output is correct
3 Correct 32 ms 48364 KB Output is correct
4 Correct 32 ms 48384 KB Output is correct
5 Correct 32 ms 48364 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 48364 KB Output is correct
2 Correct 33 ms 48364 KB Output is correct
3 Correct 32 ms 48364 KB Output is correct
4 Correct 32 ms 48384 KB Output is correct
5 Correct 32 ms 48364 KB Output is correct
6 Correct 36 ms 48364 KB Output is correct
7 Correct 37 ms 48876 KB Output is correct
8 Correct 35 ms 48620 KB Output is correct
9 Correct 39 ms 49004 KB Output is correct
10 Correct 38 ms 49004 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 48364 KB Output is correct
2 Correct 122 ms 58032 KB Output is correct
3 Correct 123 ms 57964 KB Output is correct
4 Correct 119 ms 57984 KB Output is correct
5 Correct 86 ms 54764 KB Output is correct
6 Correct 240 ms 72300 KB Output is correct
7 Correct 227 ms 72060 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 48364 KB Output is correct
2 Correct 33 ms 48364 KB Output is correct
3 Correct 32 ms 48364 KB Output is correct
4 Correct 32 ms 48384 KB Output is correct
5 Correct 32 ms 48364 KB Output is correct
6 Correct 36 ms 48364 KB Output is correct
7 Correct 37 ms 48876 KB Output is correct
8 Correct 35 ms 48620 KB Output is correct
9 Correct 39 ms 49004 KB Output is correct
10 Correct 38 ms 49004 KB Output is correct
11 Correct 33 ms 48364 KB Output is correct
12 Correct 122 ms 58032 KB Output is correct
13 Correct 123 ms 57964 KB Output is correct
14 Correct 119 ms 57984 KB Output is correct
15 Correct 86 ms 54764 KB Output is correct
16 Correct 240 ms 72300 KB Output is correct
17 Correct 227 ms 72060 KB Output is correct
18 Correct 592 ms 81512 KB Output is correct
19 Correct 549 ms 80100 KB Output is correct
20 Correct 573 ms 78148 KB Output is correct
21 Correct 162 ms 60268 KB Output is correct
22 Correct 583 ms 79896 KB Output is correct