oj.uz

Submission #863142

# Submission time Handle Problem Language Result Execution time Memory
863142 2023-10-19T16:52:24 Z MilosMilutinovic Zamjena (COCI18_zamjena) C++14
70 / 70
 77 ms 9756 KB 
#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

char a[50005][15],b[50005][15];
string x[50005],y[50005];
int p[50005],q[50005],fa[100005];

int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}

int main(){
	int n=readint();
	map<string,int> val;
	int T=1002;
	for(int i=0;i<=100000;i++) fa[i]=i;
	for(int i=1;i<=n;i++){
		scanf("%s",a[i]+1);
		if(a[i][1]<'0'||a[i][1]>'9'){
			for(int j=1;j<=strlen(a[i]+1);j++){
				x[i]+=a[i][j];
			}
			if(!val[x[i]]) val[x[i]]=T++;
		}else{
			for(int j=1;j<=strlen(a[i]+1);j++){
				p[i]=p[i]*10+(a[i][j]-'0');
			}
		}
	}
	for(int i=1;i<=n;i++){
		scanf("%s",b[i]+1);
		if(b[i][1]<'0'||b[i][1]>'9'){
			for(int j=1;j<=strlen(b[i]+1);j++){
				y[i]+=b[i][j];
			}
			if(!val[y[i]]) val[y[i]]=T++;
		}else{
			for(int j=1;j<=strlen(b[i]+1);j++){
				q[i]=q[i]*10+(b[i][j]-'0');
			}
		}
	}
	for(int i=1;i<=n;i++){
		int fx=(x[i].empty()?p[i]:val[x[i]]);
		int fy=(y[i].empty()?q[i]:val[y[i]]);
		fa[getf(fx)]=getf(fy);
	}
	bool ok=true;
	for(int i=0;i<=1000;i++){
		for(int j=i+1;j<=1000;j++){
			if(getf(i)==getf(j)) ok=false;
		}
	}
	if(ok) printf("DA\n"); else printf("NE\n");
	return 0;
}

Compilation message

zamjena.cpp: In function 'int main()':
zamjena.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for(int j=1;j<=strlen(a[i]+1);j++){
      |                ~^~~~~~~~~~~~~~~~
zamjena.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for(int j=1;j<=strlen(a[i]+1);j++){
      |                ~^~~~~~~~~~~~~~~~
zamjena.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for(int j=1;j<=strlen(b[i]+1);j++){
      |                ~^~~~~~~~~~~~~~~~
zamjena.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int j=1;j<=strlen(b[i]+1);j++){
      |                ~^~~~~~~~~~~~~~~~
zamjena.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%s",a[i]+1);
      |   ~~~~~^~~~~~~~~~~~~
zamjena.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%s",b[i]+1);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4532 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4544 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 2 ms 4688 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 5 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5212 KB Output is correct
2 Correct 21 ms 5980 KB Output is correct
3 Correct 36 ms 7252 KB Output is correct
4 Correct 44 ms 7772 KB Output is correct
5 Correct 77 ms 9756 KB Output is correct
6 Correct 52 ms 7764 KB Output is correct