Submission #44390

#TimeUsernameProblemLanguageResultExecution timeMemory
44390JustInCaseCezar (COCI16_cezar)C++17
0 / 100
2 ms592 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; const int32_t MAX_N = 105; pair< int32_t, string > words[MAX_N]; char ans[MAX_N]; class Graph { private: class Node { public: bool isVisited; vector< int32_t > v; }; bool hasEdge[MAX_N][MAX_N]; int32_t cntNodes; Node nodes[MAX_N]; public: void Init(int32_t n) { cntNodes = n; } void AddEdge(int32_t from, int32_t to) { if(!hasEdge[from][to]) { nodes[from].v.push_back(to); hasEdge[from][to] = true; } } bool DfsCheckCycle(int32_t node) { nodes[node].isVisited = true; for(int32_t x : nodes[node].v) { if(nodes[x].isVisited) { return true; } if(DfsCheckCycle(x)) { return true; } } return false; } void MarkAllNodesUnvisited() { for(int32_t i = 1; i <= cntNodes; i++) { nodes[i].isVisited = false; } } bool HasCycle() { for(int32_t i = 1; i <= cntNodes; i++) { MarkAllNodesUnvisited(); if(DfsCheckCycle(i)) { return true; } } return false; } void DfsTopoSort(int32_t node, stack< int32_t > &topoSort) { nodes[node].isVisited = true; for(int32_t x : nodes[node].v) { if(!nodes[x].isVisited) { DfsTopoSort(x, topoSort); } } topoSort.push(node); } void ComputeNewVals() { MarkAllNodesUnvisited(); stack< int32_t > st; for(int32_t i = 1; i <= cntNodes; i++) { if(!nodes[i].isVisited) { DfsTopoSort(i, st); } } char curr = 'a'; while(!st.empty()) { ans[st.top()] = curr; curr++; st.pop(); } } }; Graph g; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int32_t n; cin >> n; for(int32_t i = 1; i <= n; i++) { cin >> words[i].second; } for(int32_t i = 1; i <= n; i++) { int32_t a; cin >> a; words[a].first = i; } sort(words + 1, words + 1 + n); g.Init(26); for(int32_t i = 2; i <= n; i++) { bool foundDiff = false; for(int32_t j = 0; j < (int32_t) min(words[i - 1].second.size(), words[i].second.size()); j++) { if(words[i - 1].second[j] != words[i].second[j]) { g.AddEdge(words[i - 1].second[j] - 'a' + 1, words[i].second[j] - 'a' + 1); foundDiff = true; break; } } if(!foundDiff && words[i - 1].second.size() > words[i].second.size()) { cout << "NE" << endl; return 0; } } if(g.HasCycle()) { cout << "NE" << endl; return 0; } for(int32_t i = 1; i <= 26; i++) { ans[i] = '1'; } cout << "DA" << endl; g.ComputeNewVals(); for(int32_t i = 1; i <= 26; i++) { cout << ans[i]; } cout << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...