# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
246281 | vanic | Dijamant (COI16_dijament) | C++14 | 5 ms | 512 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <assert.h>
#include <string.h>
using namespace std;
const int maxn=1005;
map < string, int > ind;
vector < int > ms[maxn];
bool spec[maxn];
int dp[maxn];
void scan(int &a){
a=0;
char c=getchar();
while(c>='0' && c<='9'){
a*=10;
a+=c-'0';
c=getchar();
}
}
void scan1(string &s, vector < string > &v){
s.clear();
v.clear();
char c=getchar();
while(c!=' '){
s.push_back(c);
c=getchar();
}
getchar();
getchar();
c=getchar();
string s1;
while(c!=';'){
while(c!=' '){
s1.push_back(c);
c=getchar();
}
v.push_back(s1);
s1.clear();
c=getchar();
}
getchar();
}
int dfs(int x){
if(dp[x]){
return dp[x];
}
int y;
for(int i=0; i<ms[x].size(); i++){
y=dfs(ms[x][i]);
if(y==maxn){
return maxn;
}
if(y!=-1){
if(dp[x] && dp[x]!=dp[y]){
return maxn;
}
dp[x]=y;
}
}
if(!dp[x]){
if(spec[x]){
dp[x]=x;
}
else{
dp[x]=-1;
}
}
return dp[x];
}
int main(){
assert(0);
int n;
scan(n);
string s;
vector < string > v;
int p;
bool sol;
int iduc=1;
for(int i=0; i<n; i++){
scan1(s, v);
sol=1;
if(ind.find(s)!=ind.end()){
printf("greska\n");
continue;
}
for(int j=0; j<v.size(); j++){
if(ind.find(v[j])==ind.end()){
sol=0;
break;
}
}
if(!sol){
printf("greska\n");
continue;
}
memset(spec, 0, sizeof(spec));
for(int j=0; j<v.size(); j++){
spec[ind[v[j]]]=1;
}
memset(dp, 0, sizeof(dp));
for(int j=1; j<iduc; j++){
if(!dp[j]){
p=dfs(j);
if(p==maxn){
break;
}
}
}
if(p==maxn){
assert(0);
printf("greska\n");
continue;
}
printf("ok\n");
ind[s]=iduc;
for(int j=0; j<v.size(); j++){
ms[ind[v[j]]].push_back(iduc);
}
iduc++;
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |