Submission #309883


Source Code Expand

Copy
#include <iostream>
#include <stdio.h>
#include <istream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cstring>

using namespace std;

typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<long, long> pl;
typedef pair<double, double> pd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vii;
typedef vector<vl> vll;
typedef vector<double> vec;
typedef vector<vec> mat;
typedef map<int, int> mii;
void dumppi(const pi &p) {  cout << p.first  << ' ' << p.second << endl; }
typedef pair<long, long> pl;
void dumppl(const pl &p) { cout << p.first << ' ' << p.second << endl; }
typedef vector<pi> vpi;
void dumpvpi(const vpi &vec) { for (auto v : vec) { cout << '(' << v.first << ',' << v.second << ')' << ' '; } cout << endl; }
typedef vector<bool> vb;
void dumpvb(const vb &vec) { for (auto b : vec) { cout << b << ' '; } cout << endl; }
typedef vector<int> vi;
void dumpvi(const vi &vec) { for (auto i : vec) { cout << i << ' '; } cout << endl; }
typedef vector<pl> vpl;
void dumpvpi(const vpl &vec) { for (auto v : vec) { cout << '(' << v.first << ',' << v.second << ')' << ' '; } cout << endl; }
typedef vector<vi> vii;
void dumpvii(const vii &mat) {for (auto vec : mat) {for (auto v : vec){cout << v << ' ';} cout << endl;}}


// util macro
// ----------------------------------------
#define mp make_pair
#define pb push_back
//-----------------------------------------

// iterator
// ----------------------------------------
#define all(x) (x).begin(), (x).end()
// ----------------------------------------

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
//------------------------------------------

const int INF = 1e9;
const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = { 0,-1, 0, 1};

const int mod = 1000000007;
const double g = 9.8;

// POINTS
//-------------------------------------------
typedef complex<double> point;
// X : real();
// Y : imag();
double dot(point a, point b){  // inner product
    return (a * conj(b)).real();
}
double cross(point a, point b){ // outer product
    return (a * conj(b)).imag();
}
double dist(point a, point b) {
    return dot(a-b, a-b);
}
typedef vector<point> vpoint;
//-------------------------------------------

// math
//-------------------------------------------
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}
ll mod_pow(ll x, ll n) {
    if (n==0) return 1;
    ll res = mod_pow(x * x % mod, n / 2);
    if (n & 1) res = res * x % mod;
    return res;
}
ll m_fact(ll n) {
    ll res = 1; for (int i = 2; i <= n; i++) { res = res * i % mod; } return res;
}
ll mod_inverse(ll a) {
    ll x, y;
    extgcd(a, mod, x, y);
    return (mod + x % mod) % mod;
}
ll mod_fact(ll n, ll &e) {
    e = 0;
    if (n == 0) return 1;
    ll res = mod_fact(n / mod, e);
    e += n / mod;
    if (n / mod % 2 != 0) return res * (mod - m_fact(n % mod)) % mod;
    return res * m_fact(n % mod) % mod;
}

ll mod_comb(int n, int k) {
    if (n < 0 || k < 0 || n < k) return 0;
    ll e1, e2, e3;
    ll a1 = mod_fact(n, e1), a2 = mod_fact(k, e2), a3 = mod_fact(n-k, e3);
    if (e1 + e2 > e3) return 0;
    return a1 * mod_inverse(a2 * a3 % mod);
}
//-------------------------------------------


//-------------------------------------------
// Union Find
class uf {
private:
    vl _par = vl(0);
    vl _rank = vl(0);
public:
    uf(const ll n) {
        _par = vl(n); _rank = vl(n);
        for (ll i = 0; i < n; i++) {
            _par.at(i) = i;
            _rank.at(i) = 0;
        }
    }
    
    ll find(ll x) {
        if (_par.at(x) == x) { return x; }
        else { return _par.at(x) = find(_par.at(x)); }
    }
    
    void unite(ll x, ll y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (_rank.at(x) < _rank.at(y)) { _par.at(x) = y; }
        else { _par.at(y) = x; if (_rank.at(x) == _rank.at(y)) { _rank.at(x)++; } }
    }
    bool same(ll x, ll y) { return find(x) == find(y); }
};

//-------------------------------------------


#define  debu 0

template<typename T>
T readcin() {
    T x;
    cin >> x;
    return x;
}

const int MAX_V = 310;

char Ci[MAX_V];
int V;
vector<int> G[MAX_V];
vector<int> rG[MAX_V];
vector<int> vs;
bool used[MAX_V];
int cmp[MAX_V];

void add_edge(int from, int to) {
    G[from].push_back(to);
    rG[to].push_back(from);
}

void dfs(int v) {
    used[v] = true;
    for(int i = 0; i < G[v].size(); i++) {
        if (!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
}

void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); i++) {
        if (!used[rG[v][i]]) rdfs(rG[v][i], k);
    }
}

int scc() {
    memset(used, 0, sizeof(used));
    vs.clear();
    for (int v = 0; v < V; v++) {
        if (!used[v]) dfs(v);
    }
    memset(used, 0, sizeof(used));
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; i--) {
        if (!used[vs[i]]) rdfs(vs[i], k++);
    }
    return k;
}


int main(int argc, const char * argv[])
{
    ios::sync_with_stdio(false);
    
    const auto n = readcin<int>();
    V = n;
    
    const auto m = readcin<int>();
    const auto k = readcin<int>();
    
    for (int i = 0; i < n; i++) {
        Ci[i] = readcin<char>();
    }
    for (int i = 0; i < m; i++) {
        auto from = readcin<int>();
        auto to = readcin<int>();
        add_edge(--from, --to);
    }
    scc();
    
#if 0
    for (int i = 0; i < n; i++) {
        cout << cmp[i] << " ";
    }
    cout << endl;
#endif
    
    vector<tuple<int, char, int>> sortvers; // [(トポロジカルソート順, character, 頂点番号)]
    int max_scc_num = -1;
    for (int i = 0; i < n; i++) {
        sortvers.push_back(make_tuple(cmp[i], Ci[i], i));
        max_scc_num = max(max_scc_num, cmp[i]);
    }
    
    sort(sortvers.begin(), sortvers.end());
    
    
    set<int> to_vs[MAX_V];  // scc to edges
    int last_v[MAX_V];      // scc last vertex
    int first_v[MAX_V];     // scc first vertex
    for (int i = 0; i < n; i++) {
        first_v[i] = -1;
    }
    
    for (int i = 0; i < n; i++) {
        const auto x = sortvers[i];
        const auto scc_n = get<0>(x);
        const auto vn = get<2>(x);
        
        // cout << get<0>(x) << " " << get<1>(x) << " " << get<2>(x) << " " << endl;
        
        last_v[scc_n] = vn;
        if (first_v[scc_n] == -1) {
            first_v[scc_n] = vn;
        }
    }
    
    for (int i = 0; i < n; i++) {
        const auto x = sortvers[i];
        const auto scc_n = get<0>(x);
        const auto vn = get<2>(x);
        
        for (int j = 0; j < G[vn].size(); j++) {
            int toscc = cmp[G[vn][j]];
            if (scc_n != toscc) { // 自己ループはいらない
                to_vs[scc_n].insert(toscc);
            }
        }
    }
    
    
    string dp[MAX_V][MAX_V]; // 頂点番号, 長さ
    // const string inf(k, 'x');
    for (int i = 0; i < n; i++) {
        dp[i][1] = Ci[i]; // 初期化 一歩も進まなかった場合
        for (int j = 2; j <= k; j++) {
            dp[i][j] = "";
        }
    }
    
#if 0
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    
    for (int i = 0; i < n; i++) {
        cout << i;
        for (auto x : to_vs[i]) {
            cout << " " << x;
        }
        cout << endl;
    }
    cout << endl;
#endif
    
    for (int i = 0; i < n-1; i++) {
        const auto x = sortvers[i];
        const auto scc_n = get<0>(x);
        const auto vn = get<2>(x);
        
        set<int> tos;
        if (last_v[scc_n] == vn) { // sccの最後なのでばら撒く
            for (auto to_scc : to_vs[scc_n]) {
                tos.insert(first_v[to_scc]);
            }
        } else {
            tos.insert(get<2>(sortvers[i+1])); // scc内なので(sccの先頭に)だけ撒く
        }
#if 0
        cout << "tos[" << i << "]:";
        for (auto xxx : tos) {
            cout << " " << xxx;
        }
        cout << endl;
#endif
        
        // 配るdp
        for (int to : tos) {
            for (int j = 1; j <= k; j++) {
                if (dp[vn][j] == "") { continue; }
                
                // toを使う
                if (dp[to][j+1] == "") {
                    dp[to][j+1] = dp[vn][j]+Ci[to];
                } else {
                    dp[to][j+1] = min(dp[to][j+1], dp[vn][j]+Ci[to]);
                }
                // cout << vn << " " << to << " " << j+1 << " " << dp[to][j+1] << endl;
                
                // toを使わない
                if (dp[to][j] == "") {
                    dp[to][j] = dp[vn][j];
                } else {
                    dp[to][j] = min(dp[to][j], dp[vn][j]);
                }
                // cout << vn << " " << to << " " << j << " " << dp[to][j] << endl;
                
            }
        }
    }

#if 0
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
#endif

    string ans = "";
    for (int i = 0; i < n; i++) {
        if (dp[i][k] != "") {
            if (ans == "") {
                ans = dp[i][k];
            } else {
                ans = min(ans, dp[i][k]);
            }
        }
    }
    
    if (ans != "") {
        cout << ans << endl;
    } else {
        cout << "-1" << endl;
    }
}

Submission Info

Submission Time
Task C - 有向グラフ
User nida_001
Language C++11 (GCC 4.8.1)
Score 100
Code Size 10433 Byte
Status AC
Exec Time 60 ms
Memory 10220 KB

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 39 ms 1672 KB
subtask0_sample_02.txt AC 28 ms 1692 KB
subtask0_sample_03.txt AC 28 ms 1668 KB
subtask0_sample_04.txt AC 26 ms 1652 KB
subtask1_manual01.txt AC 28 ms 1668 KB
subtask1_manual02.txt AC 25 ms 1668 KB
subtask1_manual03.txt AC 26 ms 1664 KB
subtask1_manual04.txt AC 28 ms 1788 KB
subtask1_manual05.txt AC 26 ms 1664 KB
subtask1_manual06.txt AC 25 ms 1688 KB
subtask1_manual07.txt AC 27 ms 1660 KB
subtask1_manual08.txt AC 26 ms 1688 KB
subtask1_random01.txt AC 38 ms 2036 KB
subtask1_random02.txt AC 30 ms 1780 KB
subtask1_random03.txt AC 42 ms 3076 KB
subtask1_random04.txt AC 36 ms 2144 KB
subtask1_random05.txt AC 27 ms 1820 KB
subtask1_special01.txt AC 41 ms 2180 KB
subtask1_special02.txt AC 29 ms 1816 KB
subtask1_special03.txt AC 42 ms 4356 KB
subtask1_special04.txt AC 48 ms 8192 KB
subtask1_special05.txt AC 57 ms 10008 KB
subtask1_special06.txt AC 56 ms 9216 KB
subtask1_special07.txt AC 44 ms 5504 KB
subtask1_special08.txt AC 58 ms 9220 KB
subtask1_special09.txt AC 58 ms 9220 KB
subtask1_special10.txt AC 59 ms 9236 KB
subtask1_special11.txt AC 54 ms 9212 KB
subtask1_special12.txt AC 60 ms 9212 KB
subtask1_special13.txt AC 60 ms 9252 KB
subtask1_special14.txt AC 28 ms 1824 KB
subtask1_special15.txt AC 59 ms 10220 KB