# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
464678 | 2021-08-13T16:36:11 Z | ahmedfouadnew | Zamjena (COCI18_zamjena) | C++17 | 71 ms | 11440 KB |
#include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back const int mod=1e9+7; int n; string s[50001]; string s2[50001]; int sz[100001]; int par[100001]; int num[100001]; vector<pair<string,int> >vv; int its(string sss) { int ret=0; for(int i=0;i<sss.size();i++) { ret*=10; ret+=sss[i]-'0'; } return ret; } int findp(int u) { if(par[u]==u) return u; return par[u]=findp(par[u]); } void join(int u,int v) { u=findp(u); v=findp(v); if(u==v) return; if(num[u]&&num[v]&&(num[u]!=num[v])) { puts("NE"); exit(0); } if(sz[u]<sz[v]) swap(u,v); par[v]=u; sz[u]+=sz[v]; num[u]=num[u]|num[v]; return; } signed main() { int n; cin>>n; for(int i=0;i<n;i++) { cin>>s[i]; sz[i]=1; par[i]=i; if(s[i][0]<='9'&&s[i][0]>='0') num[i]=its(s[i]); else num[i]=0; } for(int i=0;i<n;i++) { cin>>s2[i]; par[n+i]=n+i; sz[n+i]=1; if(s2[i][0]<='9'&&s2[i][0]>='0') num[n+i]=its(s2[i]); else num[n+i]=0; } for(int i=0;i<n;i++) { vv.pb({s[i],i}); vv.pb({s2[i],n+i}); } sort(vv.begin(),vv.end()); for(int i=1;i<vv.size();i++) { if(vv[i].first[0]<='9'&&vv[i].first[0]>='0') continue; if(vv[i].first==vv[i-1].first) { join(vv[i].second,vv[i-1].second); } } for(int i=0;i<n;i++) { join(i,i+n); } puts("DA"); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 3404 KB | Output is correct |
2 | Correct | 2 ms | 3404 KB | Output is correct |
3 | Correct | 2 ms | 3404 KB | Output is correct |
4 | Correct | 2 ms | 3428 KB | Output is correct |
5 | Correct | 2 ms | 3432 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 3404 KB | Output is correct |
2 | Correct | 2 ms | 3404 KB | Output is correct |
3 | Correct | 2 ms | 3404 KB | Output is correct |
4 | Correct | 2 ms | 3404 KB | Output is correct |
5 | Correct | 2 ms | 3404 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 3404 KB | Output is correct |
2 | Correct | 2 ms | 3404 KB | Output is correct |
3 | Correct | 2 ms | 3404 KB | Output is correct |
4 | Correct | 2 ms | 3404 KB | Output is correct |
5 | Correct | 2 ms | 3404 KB | Output is correct |
6 | Correct | 2 ms | 3404 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 3544 KB | Output is correct |
2 | Correct | 3 ms | 3532 KB | Output is correct |
3 | Correct | 5 ms | 4012 KB | Output is correct |
4 | Correct | 5 ms | 4012 KB | Output is correct |
5 | Correct | 6 ms | 4048 KB | Output is correct |
6 | Correct | 6 ms | 4012 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 5316 KB | Output is correct |
2 | Correct | 30 ms | 7232 KB | Output is correct |
3 | Correct | 40 ms | 7736 KB | Output is correct |
4 | Correct | 53 ms | 10904 KB | Output is correct |
5 | Correct | 71 ms | 11392 KB | Output is correct |
6 | Correct | 64 ms | 11440 KB | Output is correct |