Submission #1219463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219463		TVSown	Shell (info1cup18_shell)	C++20	100 / 100	345 ms	66052 KiB

shell

///*** Sown_Vipro ***///
/// ->TEAM SELECTION TEST<- ///

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define all(s) s.begin(), s.end()
#define szz(s) int(s.size())
const string NAME = "sown";
const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
void maxi(int &x, int y){ if(x < y) x = y; }
void mini(int &x, int y){ if(x > y) x = y; };
void add(int &x, int y){ x += y; x += MOD * (x < 0); x -= MOD * (x >= MOD); };
int n, m, p;
int spe[N], ver[N], vt[N], b[N], dp[N];
vector<int> tp, e[N], adj[N];
void solve(){
    cin >> n >> m >> p;
    FOR(i, 1, p){
        int u; cin >> u;
        spe[u] = i;
        ver[i] = u;
    }

    FOR(i, 1, m){
        int u, v; cin >> u >> v;
        ++b[v];
        e[u].pb(v);
        adj[v].pb(u);
    }

    queue<int> q;
    FOR(u, 1, n) if(!b[u]) q.push(u);

    while(q.size()){
        int u = q.front(); q.pop();
        tp.pb(u);
//        cout << u << "\n";
        vt[u] = szz(tp);
        for(int v : e[u]){
            --b[v];
            if(!b[v]) q.push(v);
        }
    }

//    FOR(i, 2, p){
//        int u = ver[i];
//        if(vt[u] < vt[ver[i - 1]]){
//            cout << 11111; return;
//        }
//    }

    int j = 0;
    dp[1] = 1;

    FOR(i, 0, szz(tp) - 1){
        int u = tp[i];

        for(int v : adj[u]){
            add(dp[u], dp[v]);
        }

//        cout << u << " " << dp[u] << "\n";
        if(spe[u]){
            for(j; j < i; ++j) dp[tp[j]] = 0;
        }
    }

    cout << dp[n];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
//        freopen((NAME + ".out").c_str(), "w", stdout);
    }
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

shell.cpp: In function 'int main()':
shell.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 45 / 45
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25