Submission #286997


Source Code Expand

Copy
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<functional>
#include<complex>

using namespace std;
#define BET(a,b,c) ((a)<=(b)&&(b)<(c))
#define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++)
#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(),(x).end()
#define MP make_pair
#define CLS(x,val) memset((x) , val , sizeof(x)) 
#define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++)
typedef long long ll_t;
typedef long double ld_t;
typedef vector<int> VI;
typedef vector<VI> VVI;

typedef complex<int> xy;

struct StrongConnectComponent
{
  int n ;
  vector<bool> isvisited;
  vector<int> label; 
  vector<vector<int> > adj , inv_adj , scc;
  StrongConnectComponent(vector<vector<int> > &adj) : adj(adj)
  {
    n = (int)adj.size();
    isvisited = vector<bool>(n);
    inv_adj = vector<vector<int> >(n);
    FOR(i,n){
      FOR(j,SZ(adj[i])){
        inv_adj[adj[i][j]].push_back(i);
      }
    }
  }

  void dfs(int k , const vector<vector<int> > &g , vector<int>& lbl)
  {
    if(isvisited[k]) return;
    isvisited[k]=true;
    FOR(i,SZ(g[k])) dfs(g[k][i] , g , lbl) ;
    lbl.push_back(k);
  }

  vector<vector<int> > get_scc()
  {
    fill_n(isvisited.begin() , n , false);
    FOR(i,n) dfs(i , adj , label);
    reverse(label.begin() , label.end()) ;
    fill_n(isvisited.begin() , n , false);
    scc.clear();
    FOR(i,n) if(!isvisited[label[i]]){
      scc.push_back(vector<int>());
      dfs(label[i], inv_adj , scc.back()) ; 
    }
    return scc; 
  }
};

string memo[303][303];

VVI adj2;
vector<string> groupChars;
string inf = "{{{{{{";

string dfs(int pos, int k){
    if(k == 0) return "";
    string& ret = memo[pos][k];
    if(ret != "") return ret;

    string prefix = "";
    string val = inf;
    //cout<<pos<<" "<<k<<" "<<groupChars[pos]<<endl;
    FOR(i, SZ(groupChars[pos])+1){
        for(auto next : adj2[pos]){
            string sub = dfs(next, k - i);
            if(sub == inf) continue;
            sub = prefix + sub;
            if(val > sub) val = sub;
        }
        if(i == k){
            if(val > prefix) val = prefix;
        }

        prefix += groupChars[pos][i];
    }

    return ret = val;
}


int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    vector<char> c(n);
    FOR(i,n) cin>>c[i];
    VVI adj(n);
    FOR(i,m){
        int a,b;
        scanf("%d%d",&a,&b);
        a--; b--;
        adj[a].push_back(b);
    }

    auto scc = StrongConnectComponent(adj);
    VVI groups = scc.get_scc();
    int g = SZ(groups);
    adj2.resize(g);
    groupChars.resize(g);
    VI toGroupIndex(n);
    FOR(i,g){
        for(auto v : groups[i]){
            toGroupIndex[v] = i;
            groupChars[i] += c[v];
        }
        sort(ALL(groupChars[i]));
        //cout<<groupChars[i]<<endl;
    }
    vector<pair<int,int> > edges;
    FOR(i,n){
        int gi = toGroupIndex[i];
        for(auto v : adj[i]){
            int gv = toGroupIndex[v];
            if(gi != gv) edges.push_back(MP(gi, gv));
        }
    }
    sort(ALL(edges));
    edges.erase(unique(edges.begin(),edges.end()),edges.end());
    for(auto e : edges){
        //cout<<e.first<<" "<<e.second<<endl;
        adj2[e.first].push_back(e.second);
    }

    string ans = inf;
    FOR(i,g){
        string sub = dfs(i, k);
        if(ans > sub) ans = sub;
    }
    if(ans == inf) ans = "-1";
    cout<<ans<<endl;

    return 0;
}

Submission Info

Submission Time
Task C - 有向グラフ
User EmK
Language C++11 (GCC 4.8.1)
Score 100
Code Size 3736 Byte
Status AC
Exec Time 85 ms
Memory 4388 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:114:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
                            ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 4
AC × 32
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_manual01.txt, subtask1_manual02.txt, subtask1_manual03.txt, subtask1_manual04.txt, subtask1_manual05.txt, subtask1_manual06.txt, subtask1_manual07.txt, subtask1_manual08.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt, subtask1_special05.txt, subtask1_special06.txt, subtask1_special07.txt, subtask1_special08.txt, subtask1_special09.txt, subtask1_special10.txt, subtask1_special11.txt, subtask1_special12.txt, subtask1_special13.txt, subtask1_special14.txt, subtask1_special15.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 85 ms 1396 KB
subtask0_sample_02.txt AC 25 ms 1504 KB
subtask0_sample_03.txt AC 25 ms 1436 KB
subtask0_sample_04.txt AC 25 ms 1508 KB
subtask1_manual01.txt AC 25 ms 1568 KB
subtask1_manual02.txt AC 25 ms 1568 KB
subtask1_manual03.txt AC 25 ms 1564 KB
subtask1_manual04.txt AC 25 ms 1568 KB
subtask1_manual05.txt AC 25 ms 1440 KB
subtask1_manual06.txt AC 25 ms 1504 KB
subtask1_manual07.txt AC 25 ms 1504 KB
subtask1_manual08.txt AC 25 ms 1568 KB
subtask1_random01.txt AC 25 ms 1696 KB
subtask1_random02.txt AC 27 ms 1504 KB
subtask1_random03.txt AC 31 ms 1696 KB
subtask1_random04.txt AC 27 ms 1508 KB
subtask1_random05.txt AC 26 ms 1568 KB
subtask1_special01.txt AC 26 ms 1696 KB
subtask1_special02.txt AC 28 ms 1832 KB
subtask1_special03.txt AC 42 ms 3364 KB
subtask1_special04.txt AC 51 ms 4388 KB
subtask1_special05.txt AC 39 ms 1704 KB
subtask1_special06.txt AC 32 ms 1632 KB
subtask1_special07.txt AC 42 ms 2464 KB
subtask1_special08.txt AC 31 ms 1692 KB
subtask1_special09.txt AC 33 ms 1692 KB
subtask1_special10.txt AC 33 ms 1688 KB
subtask1_special11.txt AC 33 ms 1572 KB
subtask1_special12.txt AC 32 ms 1696 KB
subtask1_special13.txt AC 30 ms 1572 KB
subtask1_special14.txt AC 25 ms 1696 KB
subtask1_special15.txt AC 40 ms 1816 KB