Submission #1145638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145638		keisuke6	Virus Experiment (JOI19_virus)	C++20	14 / 100	347 ms	126612 KiB

virus

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> scc(vector<vector<int>> &G){ 
    int n = G.size(); 
    vector<int> S(n,-1), T = {}; 
    stack<int> s;
    
    function<void(int)> dfs1 = [&](int v){
        S[v] = 1;
        for(int x:G[v])if(S[x] == -1) dfs1(x);
        T.emplace_back(v);
    };

    for(int i=0;i<n;i++)if(S[i] == -1) dfs1(i);
    vector<vector<int>> GG(n);
    for(int i=0;i<n;i++)for(int x:G[i]) GG[x].push_back(i);
    vector<vector<int>> Ans;
    for(int &x:S) x = -1;
    reverse(T.begin(),T.end());

    function<void(int, vector<int>&)> dfs2 = [&](int v, vector<int> &c){
        S[v] = 1;
        c.push_back(v);
        for(int x:GG[v])if(S[x] == -1) dfs2(x,c);
    };

    for (int x:T){
        if (S[x] == -1){
            vector<int> c;
            dfs2(x, c);
            Ans.push_back(c);
        }
    }
    
    return Ans;
}
signed main(){
    int N,H,W;
    cin>>N>>H>>W;
    string S;
    cin>>S;
    vector<vector<int>> A(H,vector<int>(W));
    for(int i=0;i<H;i++)for(int j=0;j<W;j++) cin>>A[i][j];
    vector<int> T(4,0);
    {
        map<char,int> m;
        m['W'] = 0;
        m['E'] = 1;
        m['N'] = 2;
        m['S'] = 3;
        S += S;
        int ty = m[S[0]], now = 1;
        for(int i=1;i<2*N;i++){
            if(m[S[i]] == ty) now++;
            else{
                T[ty] = max(T[ty],now);
                now = 1;
                ty = m[S[i]];
            }
        }
        T[ty] = max(T[ty],(now == 2*N ? (int)(1e6) : now));
    }
    vector<vector<int>> G(H*W);
    for(int i=0;i<H;i++)for(int j=0;j<W-1;j++)if(A[i][j] && A[i][j+1] && A[i][j+1] <= T[0]) G[i*W+j].push_back(i*W+j+1);
    for(int i=0;i<H;i++)for(int j=1;j<W;j++)if(A[i][j] && A[i][j-1] && A[i][j-1] <= T[1]) G[i*W+j].push_back(i*W+j-1);
    for(int i=0;i<H-1;i++)for(int j=0;j<W;j++)if(A[i][j] && A[i+1][j] && A[i+1][j] <= T[2]) G[i*W+j].push_back(i*W+j+W);
    for(int i=1;i<H;i++)for(int j=0;j<W;j++)if(A[i][j] && A[i-1][j] && A[i-1][j] <= T[3]) G[i*W+j].push_back(i*W+j-W);
    vector<vector<int>> GG = scc(G);
    /*for(int i=0;i<G.size();i++){
        for(int x:G[i]) cout<<i<<' '<<x<<endl;
        cout<<endl;
    }*/
    vector<int> C(H*W);
    for(int i=0;i<GG.size();i++)for(int x:GG[i]) C[x] = i;
    int n = GG.size();
    set<pair<int,int>> s;
    for(int i=0;i<H*W;i++)for(int x:G[i]) s.insert({C[i],C[x]});
    vector<int> D(n);
    for(auto [a,b]:s) D[a] += (a != b);
    int best = 1e18, ans = 0;
    for(int i=0;i<n;i++)if(D[i] == 0 && A[GG[i][0]/W][GG[i][0]%W] != 0 && best >= GG[i].size()){
        if(best == GG[i].size()) ans += GG[i].size();
        else{
            ans = GG[i].size();
            best = GG[i].size();
        }
    }
    cout<<best<<' '<<ans<<endl;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80