Submission #464636

#TimeUsernameProblemLanguageResultExecution timeMemory
464636Sarah_MokhtarZamjena (COCI18_zamjena)C++14
0 / 70
57 ms3556 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define read freopen("in.txt","r",stdin);freopen("out.txt","w",stdout); #define LESSGO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); const ll N=1e6+10,M=505,OO=1e16,mod=1e9+7; int n,cur,valid,vid; string s; vector<int>a,b; map<string,int>idx; map<int,int>val,vis; map<int,vector<int>>adj; set<int>st; bool isDigit(char c){ return c>='0'&&c<='9'; } void dfs(int src){ vis[src]=1; for(int i:adj[src]){ if(!vis[i]){ dfs(i); } } st.insert(val[src]); } int main(){ cin>>n; for(int i=0;i<n;++i){ cin>>s; if(isDigit(s[0])) a.push_back(stoi(s)); else{ if(idx[s]) a.push_back(idx[s]); else{ idx[s]=++cur; idx[s]*=-1; a.push_back(idx[s]); } } } for(int i=0;i<n;++i){ cin>>s; if(isDigit(s[0])) b.push_back(stoi(s)); else{ if(idx[s]) b.push_back(idx[s]); else{ idx[s]=++cur; idx[s]*=-1; b.push_back(idx[s]); } } } for(int i=0;i<n;++i){ if(a[i]>0&&b[i]>0){ if(a[i]!=b[i]){ valid=0; break; } } if(a[i]<0&&b[i]<0){ adj[a[i]].push_back(b[i]); adj[b[i]].push_back(a[i]); if(!(val[a[i]]==0||val[b[i]]==0||val[a[i]]==val[b[i]])){ valid=0; break; }else{ val[a[i]]=max(val[a[i]],val[b[i]]); val[b[i]]=max(val[a[i]],val[b[i]]); } } if(a[i]>0&&b[i]<0){ if(!(val[b[i]]==0||val[b[i]]==a[i])){ valid=0; break; }else val[b[i]]=a[i]; } if(a[i]<0&&b[i]>0){ if(!(val[a[i]]==0||val[a[i]]==b[i])){ valid=0; break; }else val[a[i]]=b[i]; } } for(int i=0;i<n;++i){ if(a[i]<0&&!vis[a[i]]){ st.clear(); dfs(a[i]); if(st.size()>1){ valid=0; break; } } } if(valid==0){ puts("NE"); return 0; } for(int i=0;i<n;++i){ if(b[i]<0&&!vis[b[i]]){ st.clear(); dfs(b[i]); if(st.size()>1){ valid=0; break; } } } puts(valid?"DA":"NE"); }
#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...