Submission #1403763
Source Code Expand
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; /** * Strong connected components. * Header requirement: algorithm, cassert, set, vector * Verified by: AtCoder ARC010 (http://arc010.contest.atcoder.jp/submissions/1015294) * yukicoder No. 19 (http://yukicoder.me/submissions/141513) */ class SCC { private: int n; int ncc; typedef std::vector<int> vi; std::vector<vi> g; // graph in adjacent list std::vector<vi> rg; // reverse graph vi vs; std::vector<bool> used; vi cmp; public: SCC(int n): n(n), ncc(-1), g(n), rg(n), vs(n), used(n), cmp(n) {} void add_edge(int from, int to) { g[from].push_back(to); rg[to].push_back(from); } private: 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); } } } public: int scc() { std::fill(used.begin(), used.end(), 0); vs.clear(); for (int v = 0; v < n; ++v) { if (!used[v]) { dfs(v); } } std::fill(used.begin(), used.end(), 0); int k = 0; for (int i = vs.size() - 1; i >= 0; --i) { if (!used[vs[i]]) { rdfs(vs[i], k++); } } return ncc = k; } std::vector<int> top_order() const { if (ncc == -1) assert(0); return cmp; } std::vector<std::vector<int> > scc_components(void) const { if (ncc == -1) assert(0); std::vector<std::vector<int> > ret(ncc); for (int i = 0; i < n; ++i) { ret[cmp[i]].push_back(i); } return ret; } /* * Returns a dag whose vertices are scc's, and whose edges are those of the original graph, in the adjacent-list format. */ std::vector<std::vector<int> > dag() const { if (ncc == -1) { assert(0); } typedef std::set<int> si; std::vector<si> ret(ncc); for (int i = 0; i < g.size(); ++i) { for (int j = 0; j < g[i].size(); ++j) { int to = g[i][j]; if (cmp[i] != cmp[to]) { assert (cmp[i] < cmp[to]); ret[cmp[i]].insert(cmp[to]); } } } std::vector<std::vector<int> > vret(ncc); for (int i = 0; i < ncc; ++i) { vret[i] = std::vector<int>(ret[i].begin(), ret[i].end()); } return vret; } std::vector<std::vector<int> > rdag() const { if (ncc == -1) { assert(0); } typedef std::set<int> si; std::vector<si> ret(ncc); for (int i = 0; i < (int) g.size(); ++i) { for (int j = 0; j < (int) g[i].size(); ++j) { int to = g[i][j]; if (cmp[i] != cmp[to]) { assert (cmp[i] < cmp[to]); ret[cmp[to]].insert(cmp[i]); } } } std::vector<std::vector<int> > vret(ncc); for (int i = 0; i < ncc; ++i) { vret[i] = std::vector<int>(ret[i].begin(), ret[i].end()); } return vret; } }; const int inf = 1000; int main(void){ int n; cin >> n; VI a(n); vector<PI> pool; REP(i, 0, n) { cin >> a[i]; pool.push_back(PI(a[i], i)); } sort(pool.begin(), pool.end()); int h, w; cin >> h >> w; vector<VI> b(h, VI(w)); vector<PI> mi(n, PI(inf, inf)), ma(n, PI(-inf, -inf)); REP(i, 0, h) { REP(j, 0, w) { cin >> b[i][j]; int c = b[i][j]; mi[c].first = min(mi[c].first, i); mi[c].second = min(mi[c].second, j); ma[c].first = max(ma[c].first, i); ma[c].second = max(ma[c].second, j); } } // Collect constraints, O(nhw) vector<VI> cons(n, VI(n, 0)); REP(i, 0, h) { REP(j, 0, w) { int c = b[i][j]; REP(k, 0, n) { if (k == c) { continue; } if (mi[k].first <= i && i <= ma[k].first && mi[k].second <= j && j <= ma[k].second) { cons[k][c] = 1; // k -> c } } } } SCC scc(n); REP(i, 0, n) { REP(j, 0, n) { if (cons[i][j]) { scc.add_edge(i, j); } } } int ncc = scc.scc(); if (ncc < n) { cout << 0 << endl; return 0; } vector<VI> dist(n, VI(n, inf)); REP(i, 0, n) { REP(j, 0, n) { dist[i][j] = cons[i][j] ? 0 : inf; } } REP(k, 0, n) { REP(i, 0, n) { REP(j, 0, n) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } assert (n <= 10); // Try all possibilities, O(n!n^2) VI perm(n); REP(i, 0, n) { perm[i] = i; } bool ok = false; do { bool valid = true; REP(i, 0, n) { REP(j, 0, n) { // i -> j implies a[perm[i]] < a[perm[j]] if (cons[i][j] && a[perm[i]] >= a[perm[j]]) { valid = false; } } } if (not valid) { continue; } ok = true; } while (next_permutation(perm.begin(), perm.end()) && not ok); cout << (ok ? 1 : 0) << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 天下一芸術 |
User | kobae964 |
Language | C++14 (GCC 5.4.1) |
Score | 75 |
Code Size | 5245 Byte |
Status | RE |
Exec Time | 533 ms |
Memory | 384 KB |
Judge Result
Set Name | small | medium | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 35 / 35 | 40 / 40 | 0 / 35 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
small | 00_sample0.txt, 00_sample1.txt, 00_sample2.txt, 00_sample3.txt, 01_manual1.txt, 01_manual2.txt, 01_manual3.txt, 01_manual4.txt, 01_manual5.txt, 01_manual6.txt, 02_small100.txt, 02_small101.txt, 02_small102.txt, 02_small103.txt, 02_small104.txt, 02_small105.txt, 02_small106.txt, 02_small107.txt, 02_small108.txt, 02_small109.txt, 02_small110.txt, 02_small111.txt, 02_small112.txt, 02_small113.txt, 02_small114.txt, 02_small115.txt, 02_small116.txt, 02_small117.txt, 02_small118.txt, 02_small119.txt, 02_small120.txt, 03_small_b1.txt, 03_small_b2.txt, 03_small_b3.txt |
medium | 00_sample0.txt, 00_sample1.txt, 00_sample2.txt, 00_sample3.txt, 01_manual1.txt, 01_manual2.txt, 01_manual3.txt, 01_manual4.txt, 01_manual5.txt, 01_manual6.txt, 02_small100.txt, 02_small101.txt, 02_small102.txt, 02_small103.txt, 02_small104.txt, 02_small105.txt, 02_small106.txt, 02_small107.txt, 02_small108.txt, 02_small109.txt, 02_small110.txt, 02_small111.txt, 02_small112.txt, 02_small113.txt, 02_small114.txt, 02_small115.txt, 02_small116.txt, 02_small117.txt, 02_small118.txt, 02_small119.txt, 02_small120.txt, 03_small_b1.txt, 03_small_b2.txt, 03_small_b3.txt, 11_manual0.txt, 11_manual1.txt, 12_medium100.txt, 12_medium101.txt, 12_medium102.txt, 12_medium103.txt, 12_medium104.txt, 12_medium105.txt, 12_medium106.txt, 12_medium107.txt, 12_medium108.txt, 12_medium109.txt, 12_medium110.txt, 12_medium111.txt, 12_medium112.txt, 12_medium113.txt, 12_medium114.txt, 12_medium115.txt, 12_medium116.txt, 12_medium117.txt, 12_medium118.txt, 12_medium119.txt, 12_medium120.txt, 12_medium121.txt, 12_medium122.txt, 12_medium123.txt, 12_medium124.txt, 12_medium125.txt, 12_medium126.txt, 12_medium127.txt, 12_medium128.txt, 12_medium129.txt |
All | 00_sample0.txt, 00_sample1.txt, 00_sample2.txt, 00_sample3.txt, 01_manual1.txt, 01_manual2.txt, 01_manual3.txt, 01_manual4.txt, 01_manual5.txt, 01_manual6.txt, 02_small100.txt, 02_small101.txt, 02_small102.txt, 02_small103.txt, 02_small104.txt, 02_small105.txt, 02_small106.txt, 02_small107.txt, 02_small108.txt, 02_small109.txt, 02_small110.txt, 02_small111.txt, 02_small112.txt, 02_small113.txt, 02_small114.txt, 02_small115.txt, 02_small116.txt, 02_small117.txt, 02_small118.txt, 02_small119.txt, 02_small120.txt, 03_small_b1.txt, 03_small_b2.txt, 03_small_b3.txt, 11_manual0.txt, 11_manual1.txt, 12_medium100.txt, 12_medium101.txt, 12_medium102.txt, 12_medium103.txt, 12_medium104.txt, 12_medium105.txt, 12_medium106.txt, 12_medium107.txt, 12_medium108.txt, 12_medium109.txt, 12_medium110.txt, 12_medium111.txt, 12_medium112.txt, 12_medium113.txt, 12_medium114.txt, 12_medium115.txt, 12_medium116.txt, 12_medium117.txt, 12_medium118.txt, 12_medium119.txt, 12_medium120.txt, 12_medium121.txt, 12_medium122.txt, 12_medium123.txt, 12_medium124.txt, 12_medium125.txt, 12_medium126.txt, 12_medium127.txt, 12_medium128.txt, 12_medium129.txt, 21_manual0.txt, 21_manual1.txt, 21_manual10.txt, 21_manual11.txt, 21_manual12.txt, 21_manual13.txt, 21_manual2.txt, 21_manual3.txt, 21_manual4.txt, 21_manual5.txt, 21_manual6.txt, 21_manual7.txt, 21_manual8.txt, 21_manual9.txt, 21_manual_L0.txt, 21_manual_L1.txt, 21_manual_L2.txt, 21_manual_L3.txt, 21_manual_L4.txt, 21_manual_L5.txt, 21_manual_L6.txt, 21_manual_L7.txt, 21_manual_L8.txt, 22_hard100.txt, 22_hard101.txt, 22_hard1011.txt, 22_hard102.txt, 22_hard103.txt, 22_hard104.txt, 22_hard105.txt, 22_hard106.txt, 22_hard107.txt, 22_hard108.txt, 22_hard109.txt, 22_hard110.txt, 22_hard111.txt, 22_hard112.txt, 22_hard113.txt, 22_hard114.txt, 22_hard1140.txt, 22_hard115.txt, 22_hard116.txt, 22_hard117.txt, 22_hard118.txt, 22_hard119.txt, 22_hard120.txt, 22_hard121.txt, 22_hard122.txt, 22_hard123.txt, 22_hard124.txt, 22_hard125.txt, 22_hard126.txt, 22_hard127.txt, 22_hard128.txt, 22_hard129.txt, 22_hard130.txt, 22_hard131.txt, 22_hard132.txt, 22_hard133.txt, 22_hard134.txt, 22_hard135.txt, 22_hard154.txt, 22_hard2096.txt, 22_hard275.txt, 22_hard345.txt, 22_hard351.txt, 22_hard437.txt, 22_hard442.txt, 22_hard524.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample0.txt | AC | 1 ms | 256 KB |
00_sample1.txt | AC | 1 ms | 256 KB |
00_sample2.txt | AC | 1 ms | 256 KB |
00_sample3.txt | AC | 1 ms | 256 KB |
01_manual1.txt | AC | 1 ms | 256 KB |
01_manual2.txt | AC | 1 ms | 256 KB |
01_manual3.txt | AC | 1 ms | 256 KB |
01_manual4.txt | AC | 1 ms | 256 KB |
01_manual5.txt | AC | 1 ms | 256 KB |
01_manual6.txt | AC | 1 ms | 256 KB |
02_small100.txt | AC | 1 ms | 256 KB |
02_small101.txt | AC | 1 ms | 256 KB |
02_small102.txt | AC | 1 ms | 256 KB |
02_small103.txt | AC | 1 ms | 256 KB |
02_small104.txt | AC | 1 ms | 256 KB |
02_small105.txt | AC | 1 ms | 256 KB |
02_small106.txt | AC | 1 ms | 256 KB |
02_small107.txt | AC | 1 ms | 256 KB |
02_small108.txt | AC | 1 ms | 256 KB |
02_small109.txt | AC | 1 ms | 256 KB |
02_small110.txt | AC | 1 ms | 256 KB |
02_small111.txt | AC | 1 ms | 256 KB |
02_small112.txt | AC | 1 ms | 256 KB |
02_small113.txt | AC | 1 ms | 256 KB |
02_small114.txt | AC | 1 ms | 256 KB |
02_small115.txt | AC | 1 ms | 256 KB |
02_small116.txt | AC | 1 ms | 256 KB |
02_small117.txt | AC | 1 ms | 256 KB |
02_small118.txt | AC | 1 ms | 256 KB |
02_small119.txt | AC | 1 ms | 256 KB |
02_small120.txt | AC | 1 ms | 256 KB |
03_small_b1.txt | AC | 1 ms | 256 KB |
03_small_b2.txt | AC | 1 ms | 256 KB |
03_small_b3.txt | AC | 1 ms | 256 KB |
11_manual0.txt | AC | 3 ms | 256 KB |
11_manual1.txt | AC | 8 ms | 384 KB |
12_medium100.txt | AC | 5 ms | 384 KB |
12_medium101.txt | AC | 6 ms | 384 KB |
12_medium102.txt | AC | 8 ms | 384 KB |
12_medium103.txt | AC | 8 ms | 384 KB |
12_medium104.txt | AC | 8 ms | 384 KB |
12_medium105.txt | AC | 49 ms | 384 KB |
12_medium106.txt | AC | 24 ms | 384 KB |
12_medium107.txt | AC | 8 ms | 384 KB |
12_medium108.txt | AC | 4 ms | 256 KB |
12_medium109.txt | AC | 1 ms | 256 KB |
12_medium110.txt | AC | 8 ms | 384 KB |
12_medium111.txt | AC | 8 ms | 384 KB |
12_medium112.txt | AC | 49 ms | 384 KB |
12_medium113.txt | AC | 8 ms | 384 KB |
12_medium114.txt | AC | 4 ms | 256 KB |
12_medium115.txt | AC | 48 ms | 384 KB |
12_medium116.txt | AC | 9 ms | 384 KB |
12_medium117.txt | AC | 1 ms | 256 KB |
12_medium118.txt | AC | 1 ms | 256 KB |
12_medium119.txt | AC | 2 ms | 256 KB |
12_medium120.txt | AC | 47 ms | 384 KB |
12_medium121.txt | AC | 48 ms | 384 KB |
12_medium122.txt | AC | 7 ms | 384 KB |
12_medium123.txt | AC | 13 ms | 384 KB |
12_medium124.txt | AC | 8 ms | 384 KB |
12_medium125.txt | AC | 8 ms | 384 KB |
12_medium126.txt | AC | 1 ms | 256 KB |
12_medium127.txt | AC | 1 ms | 256 KB |
12_medium128.txt | AC | 8 ms | 384 KB |
12_medium129.txt | AC | 6 ms | 384 KB |
21_manual0.txt | RE | 116 ms | 256 KB |
21_manual1.txt | RE | 97 ms | 256 KB |
21_manual10.txt | RE | 97 ms | 256 KB |
21_manual11.txt | RE | 97 ms | 256 KB |
21_manual12.txt | RE | 97 ms | 256 KB |
21_manual13.txt | RE | 96 ms | 256 KB |
21_manual2.txt | RE | 97 ms | 256 KB |
21_manual3.txt | RE | 99 ms | 256 KB |
21_manual4.txt | RE | 97 ms | 256 KB |
21_manual5.txt | RE | 97 ms | 256 KB |
21_manual6.txt | RE | 98 ms | 256 KB |
21_manual7.txt | RE | 98 ms | 256 KB |
21_manual8.txt | RE | 99 ms | 256 KB |
21_manual9.txt | RE | 98 ms | 256 KB |
21_manual_L0.txt | RE | 97 ms | 256 KB |
21_manual_L1.txt | RE | 105 ms | 384 KB |
21_manual_L2.txt | RE | 106 ms | 384 KB |
21_manual_L3.txt | RE | 105 ms | 384 KB |
21_manual_L4.txt | RE | 105 ms | 384 KB |
21_manual_L5.txt | AC | 9 ms | 384 KB |
21_manual_L6.txt | AC | 9 ms | 384 KB |
21_manual_L7.txt | AC | 9 ms | 384 KB |
21_manual_L8.txt | AC | 9 ms | 384 KB |
22_hard100.txt | AC | 6 ms | 384 KB |
22_hard101.txt | AC | 533 ms | 384 KB |
22_hard1011.txt | RE | 105 ms | 384 KB |
22_hard102.txt | RE | 108 ms | 384 KB |
22_hard103.txt | AC | 9 ms | 384 KB |
22_hard104.txt | AC | 9 ms | 384 KB |
22_hard105.txt | RE | 104 ms | 384 KB |
22_hard106.txt | RE | 106 ms | 384 KB |
22_hard107.txt | AC | 9 ms | 384 KB |
22_hard108.txt | AC | 1 ms | 256 KB |
22_hard109.txt | RE | 98 ms | 256 KB |
22_hard110.txt | RE | 105 ms | 384 KB |
22_hard111.txt | RE | 106 ms | 384 KB |
22_hard112.txt | RE | 106 ms | 384 KB |
22_hard113.txt | AC | 9 ms | 384 KB |
22_hard114.txt | AC | 9 ms | 384 KB |
22_hard1140.txt | RE | 97 ms | 256 KB |
22_hard115.txt | RE | 105 ms | 384 KB |
22_hard116.txt | RE | 97 ms | 256 KB |
22_hard117.txt | AC | 1 ms | 256 KB |
22_hard118.txt | RE | 105 ms | 384 KB |
22_hard119.txt | RE | 106 ms | 384 KB |
22_hard120.txt | RE | 106 ms | 384 KB |
22_hard121.txt | RE | 105 ms | 384 KB |
22_hard122.txt | RE | 99 ms | 256 KB |
22_hard123.txt | AC | 4 ms | 256 KB |
22_hard124.txt | RE | 98 ms | 256 KB |
22_hard125.txt | RE | 97 ms | 256 KB |
22_hard126.txt | AC | 1 ms | 256 KB |
22_hard127.txt | RE | 105 ms | 384 KB |
22_hard128.txt | RE | 105 ms | 384 KB |
22_hard129.txt | AC | 9 ms | 384 KB |
22_hard130.txt | AC | 8 ms | 384 KB |
22_hard131.txt | RE | 106 ms | 384 KB |
22_hard132.txt | RE | 97 ms | 256 KB |
22_hard133.txt | RE | 97 ms | 256 KB |
22_hard134.txt | RE | 105 ms | 384 KB |
22_hard135.txt | RE | 107 ms | 384 KB |
22_hard154.txt | RE | 105 ms | 384 KB |
22_hard2096.txt | RE | 98 ms | 256 KB |
22_hard275.txt | RE | 104 ms | 384 KB |
22_hard345.txt | RE | 98 ms | 256 KB |
22_hard351.txt | RE | 99 ms | 256 KB |
22_hard437.txt | RE | 104 ms | 384 KB |
22_hard442.txt | RE | 106 ms | 384 KB |
22_hard524.txt | RE | 106 ms | 384 KB |