| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 246271 |
2020-07-08T13:51:35 Z |
vanic |
Dijamant (COI16_dijament) |
C++14 |
|
83 ms |
4092 KB |
#include <cstdio>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <string.h>
using namespace std;
const int maxn=1005;
map < string, int > ind;
vector < int > ms[maxn];
bool spec[maxn];
vector < int > svi;
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(){
int n;
scan(n);
string s;
vector < string > v;
int p;
bool sol;
for(int i=0; i<n; i++){
scan1(s, v);
sol=1;
if(ind[s]){
printf("greska\n");
continue;
}
for(int j=0; j<v.size(); j++){
if(!ind[v[j]]){
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));
// cout << "Na " << s << ": ";
for(int j=0; j<svi.size(); j++){
if(!dp[svi[j]]){
p=dfs(svi[j]);
// printf("%d ", dp[svi[j]]);
if(p==maxn){
break;
}
}
}
// printf("\n");
if(p==maxn){
printf("greska\n");
continue;
}
printf("ok\n");
ind[s]=i+1;
svi.push_back(i+1);
for(int j=0; j<v.size(); j++){
ms[ind[v[j]]].push_back(ind[s]);
}
}
return 0;
}
Compilation message
dijament.cpp: In function 'int dfs(int)':
dijament.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<ms[x].size(); i++){
~^~~~~~~~~~~~~
dijament.cpp: In function 'int main()':
dijament.cpp:96:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<v.size(); j++){
~^~~~~~~~~
dijament.cpp:107:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<v.size(); j++){
~^~~~~~~~~
dijament.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<svi.size(); j++){
~^~~~~~~~~~~
dijament.cpp:129:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<v.size(); j++){
~^~~~~~~~~
dijament.cpp:122:3: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(p==maxn){
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
4092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
