| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 91195 | 2018-12-26T13:53:05 Z | nikolapesic2802 | Cezar (COCI16_cezar) | C++14 | 347 ms | 66512 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
os << '{';
for(int i=0;i<sz(a);i++)
{
if(i>0&&i<sz(a))
os << ", ";
os << a[i];
}
os << '}';
return os;
}
const int N=26;
vector<vector<int> > graf(N);
vector<int> visited(N);
void dfs(int tr)
{
if(visited[tr])
{
printf("NE\n");
exit(0);
}
visited[tr]=1;
for(auto p:graf[tr])
dfs(p);
visited[tr]=0;
}
vector<int> top;
void topo(int tr)
{
if(visited[tr])
return;
for(auto p:graf[tr])
topo(p);
top.pb(tr);
}
int main()
{
int n;
scanf("%i",&n);
vector<string> niz(n);
vector<string> prvo(n);
for(int i=0;i<n;i++)
cin >> prvo[i];
for(int i=0;i<n;i++)
{
int x;
scanf("%i",&x);
x--;
niz[i]=prvo[x];
}
/*for(int i=0;i<n;i++)
cout << niz[i] << endl;*/
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
int si=niz[i].size();
int sj=niz[j].size();
if(si<sj)
{
if(niz[j].substr(0,si)==niz[i])
{
printf("NE\n");
return 0;
}
}
}
}
for(int i=1;i<n;i++)
{
for(int j=0;j<min((int)niz[i].size(),(int)niz[i-1].size());j++)
{
if(niz[i][j]!=niz[i-1][j])
{
bool test=true;
for(auto p:graf[niz[i-1][j]-'a'])
{
if(p==niz[i][j]-'a')
test=false;
}
if(test)
graf[niz[i][j]-'a'].pb(niz[i-1][j]-'a');
break;
}
}
}
for(int i=0;i<N;i++)
{
fill(all(visited),0);
dfs(i);
}
int tr=0;
vector<int> degree(N);
for(int i=0;i<N;i++)
{
for(auto p:graf[i])
{
degree[p]++;
}
}
fill(all(visited),0);
for(int i=0;i<N;i++)
if(degree[i]==0)
topo(i);
//reverse(all(top));
vector<int> sol(N,-1);
for(int i=0;i<top.size();i++)
{
sol[top[i]]=i;
}
printf("DA\n");
for(int i=0;i<N;i++)
{
printf("%c",sol[i]+'a');
}
printf("\n");
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 256 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 5 ms | 1520 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 1520 KB | Output is correct |
| 2 | Correct | 2 ms | 1520 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 194 ms | 66256 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 347 ms | 66512 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 2 ms | 66512 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 112 ms | 66512 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 2 ms | 66512 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 2 ms | 66512 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 2 ms | 66512 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 | Halted | 0 ms | 0 KB | - |