답안 #14913 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
14913	2015-07-06T00:30:22 Z	gs13068	Palembang Bridges (APIO15_bridge)	C++	63 / 100	493 ms	6328 KB

bridge

#include<cstdio>
#include<algorithm>

int p[111111];
int s[111111];
int q[111111];
int t[111111];
char pp[11],qq[11];
std::pair<int,int> d[444444];
int dn;

int main()
{
	//freopen("input","r",stdin);
	long long res=0;
	int i,j,n,m;
	int fir,sec;
	long long min,now,ang;
	scanf("%d%d",&m,&n);
	if(m==1)
	{
		j=0;
        for(i=0;i<n;i++)
        {
			scanf("%s%d%s%d",pp,&s[i],qq,&t[i]);
			p[i]=pp[0]-'A';
			q[i]=qq[0]-'A';
			if(p[i]!=q[i])
			{
				j++;
				d[dn++]=std::make_pair(std::min(s[i],t[i]),-1);
				d[dn++]=std::make_pair(std::max(s[i],t[i]),-1);
			}
        }
        std::sort(d,d+dn);
        for(i=0;i<dn;i++)
        {
			j+=d[i].second;
            if(j<=0)break;
        }
        for(j=0;j<n;j++)
        {
			if(p[j]!=q[j])res+=std::abs(s[j]-d[i].first)+std::abs(t[j]-d[i].first)+1;
			else res+=std::abs(s[j]-t[j]);
        }
        printf("%lld\n",res);
		return 0;
	}

	for(i=0;i<n;i++)
	{
		scanf("%s%d%s%d",pp,&s[i],qq,&t[i]);
		p[i]=pp[0]-'A';
		q[i]=qq[0]-'A';
	}

	if(n<=1000)
	{
		res=9e18;
        for(i=0;i<n;i++)
        {
			fir=s[i];
			dn=0;
			for(j=0;j<n;j++)if(p[j]!=q[j]&&(std::max(s[j],t[j])<fir||std::min(s[j],t[j])>fir))
			{
				d[dn++]=std::make_pair(std::min(fir,s[j]+t[j]-fir),1);
				d[dn++]=std::make_pair(std::max(fir,s[j]+t[j]-fir),1);
				d[dn++]=std::make_pair(std::min(s[j],t[j]),-1);
				d[dn++]=std::make_pair(std::max(s[j],t[j]),-1);
			}
			std::sort(d,d+dn);
			min=now=ang=0;
			sec=0;

			for(j=0;j<dn;j++)
			{
				if(j)now+=ang*(d[j].first-d[j-1].first);
				ang+=d[j].second;
				if(now>min)
				{
					min=now;
					sec=d[j].first;
				}
			}

			now=0;
			for(j=0;j<n;j++)
			{
				if(p[j]!=q[j])now+=std::min(std::abs(s[j]-fir)+std::abs(t[j]-fir),std::abs(s[j]-sec)+std::abs(t[j]-sec))+1;
				else now+=std::abs(s[j]-t[j]);
			}

			res=std::min(res,now);

			fir=t[i];
			dn=0;
			for(j=0;j<n;j++)if(p[j]!=q[j]&&(std::max(s[j],t[j])<fir||std::min(s[j],t[j])>fir))
			{
				d[dn++]=std::make_pair(std::min(fir,s[j]+t[j]-fir),1);
				d[dn++]=std::make_pair(std::max(fir,s[j]+t[j]-fir),1);
				d[dn++]=std::make_pair(std::min(s[j],t[j]),-1);
				d[dn++]=std::make_pair(std::max(s[j],t[j]),-1);
			}
			std::sort(d,d+dn);
			min=now=ang=0;
			sec=0;

			for(j=0;j<dn;j++)
			{
				if(j)now+=ang*(d[j].first-d[j-1].first);
				ang+=d[j].second;
				if(now>min)
				{
					min=now;
					sec=d[j].first;
				}
			}

			now=0;
			for(j=0;j<n;j++)
			{
				if(p[j]!=q[j])now+=std::min(std::abs(s[j]-fir)+std::abs(t[j]-fir),std::abs(s[j]-sec)+std::abs(t[j]-sec))+1;
				else now+=std::abs(s[j]-t[j]);
			}

			res=std::min(res,now);
        }

        printf("%lld\n",res);
        return 0;
	}

	sec=s[0];
	for(i=1;i<=5;i++)
	{
		fir=sec;
		dn=0;
        for(j=0;j<n;j++)if(p[j]!=q[j]&&(std::max(s[j],t[j])<fir||std::min(s[j],t[j])>fir))
        {
            d[dn++]=std::make_pair(std::min(fir,s[j]+t[j]-fir),1);
            d[dn++]=std::make_pair(std::max(fir,s[j]+t[j]-fir),1);
            d[dn++]=std::make_pair(std::min(s[j],t[j]),-1);
            d[dn++]=std::make_pair(std::max(s[j],t[j]),-1);
        }
        std::sort(d,d+dn);
		min=now=ang=0;
		sec=s[i%n];
		for(j=0;j<dn;j++)
		{
			if(j)now+=ang*(d[j].first-d[j-1].first);
			ang+=d[j].second;
			if(now>min)
			{
				min=now;
				sec=d[j].first;
			}
		}
	}

	for(j=0;j<n;j++)
	{
		if(p[j]!=q[j])res+=std::min(std::abs(s[j]-fir)+std::abs(t[j]-fir),std::abs(s[j]-sec)+std::abs(t[j]-sec))+1;
		else res+=std::abs(s[j]-t[j]);
	}

	printf("%lld\n",res);
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:19:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&m,&n);
                     ^
bridge.cpp:25:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s%d%s%d",pp,&s[i],qq,&t[i]);
                                       ^
bridge.cpp:52:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%s%d",pp,&s[i],qq,&t[i]);
                                      ^

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6328 KB	Output is correct
2	Correct	0 ms	6328 KB	Output is correct
3	Correct	0 ms	6328 KB	Output is correct
4	Correct	0 ms	6328 KB	Output is correct
5	Correct	0 ms	6328 KB	Output is correct
6	Correct	0 ms	6328 KB	Output is correct
7	Correct	0 ms	6328 KB	Output is correct
8	Correct	0 ms	6328 KB	Output is correct
9	Correct	3 ms	6328 KB	Output is correct
10	Correct	0 ms	6328 KB	Output is correct
11	Correct	0 ms	6328 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6328 KB	Output is correct
2	Correct	0 ms	6328 KB	Output is correct
3	Correct	0 ms	6328 KB	Output is correct
4	Correct	0 ms	6328 KB	Output is correct
5	Correct	0 ms	6328 KB	Output is correct
6	Correct	0 ms	6328 KB	Output is correct
7	Correct	3 ms	6328 KB	Output is correct
8	Correct	3 ms	6328 KB	Output is correct
9	Correct	3 ms	6328 KB	Output is correct
10	Correct	0 ms	6328 KB	Output is correct
11	Correct	0 ms	6328 KB	Output is correct
12	Correct	53 ms	6328 KB	Output is correct
13	Correct	63 ms	6328 KB	Output is correct
14	Correct	63 ms	6328 KB	Output is correct
15	Correct	43 ms	6328 KB	Output is correct
16	Correct	43 ms	6328 KB	Output is correct
17	Correct	39 ms	6328 KB	Output is correct
18	Correct	53 ms	6328 KB	Output is correct
19	Correct	69 ms	6328 KB	Output is correct
20	Correct	46 ms	6328 KB	Output is correct
21	Correct	63 ms	6328 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6328 KB	Output is correct
2	Correct	0 ms	6328 KB	Output is correct
3	Correct	0 ms	6328 KB	Output is correct
4	Correct	3 ms	6328 KB	Output is correct
5	Correct	3 ms	6328 KB	Output is correct
6	Correct	0 ms	6328 KB	Output is correct
7	Correct	0 ms	6328 KB	Output is correct
8	Correct	3 ms	6328 KB	Output is correct
9	Correct	3 ms	6328 KB	Output is correct
10	Correct	3 ms	6328 KB	Output is correct
11	Correct	3 ms	6328 KB	Output is correct
12	Correct	3 ms	6328 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6328 KB	Output is correct
2	Correct	0 ms	6328 KB	Output is correct
3	Correct	0 ms	6328 KB	Output is correct
4	Correct	3 ms	6328 KB	Output is correct
5	Correct	0 ms	6328 KB	Output is correct
6	Correct	3 ms	6328 KB	Output is correct
7	Correct	0 ms	6328 KB	Output is correct
8	Correct	3 ms	6328 KB	Output is correct
9	Correct	3 ms	6328 KB	Output is correct
10	Correct	3 ms	6328 KB	Output is correct
11	Correct	3 ms	6328 KB	Output is correct
12	Correct	3 ms	6328 KB	Output is correct
13	Correct	49 ms	6328 KB	Output is correct
14	Correct	349 ms	6328 KB	Output is correct
15	Correct	319 ms	6328 KB	Output is correct
16	Correct	3 ms	6328 KB	Output is correct
17	Correct	96 ms	6328 KB	Output is correct
18	Correct	49 ms	6328 KB	Output is correct
19	Correct	19 ms	6328 KB	Output is correct
20	Correct	373 ms	6328 KB	Output is correct
21	Correct	169 ms	6328 KB	Output is correct
22	Correct	489 ms	6328 KB	Output is correct
23	Correct	189 ms	6328 KB	Output is correct
24	Correct	476 ms	6328 KB	Output is correct

Subtask #5
0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6328 KB	Output is correct
2	Correct	0 ms	6328 KB	Output is correct
3	Correct	3 ms	6328 KB	Output is correct
4	Correct	0 ms	6328 KB	Output is correct
5	Correct	3 ms	6328 KB	Output is correct
6	Correct	3 ms	6328 KB	Output is correct
7	Correct	3 ms	6328 KB	Output is correct
8	Correct	3 ms	6328 KB	Output is correct
9	Correct	3 ms	6328 KB	Output is correct
10	Correct	3 ms	6328 KB	Output is correct
11	Correct	0 ms	6328 KB	Output is correct
12	Correct	3 ms	6328 KB	Output is correct
13	Correct	53 ms	6328 KB	Output is correct
14	Correct	353 ms	6328 KB	Output is correct
15	Correct	329 ms	6328 KB	Output is correct
16	Correct	6 ms	6328 KB	Output is correct
17	Correct	103 ms	6328 KB	Output is correct
18	Correct	43 ms	6328 KB	Output is correct
19	Correct	13 ms	6328 KB	Output is correct
20	Correct	393 ms	6328 KB	Output is correct
21	Correct	156 ms	6328 KB	Output is correct
22	Correct	493 ms	6328 KB	Output is correct
23	Correct	206 ms	6328 KB	Output is correct
24	Correct	469 ms	6328 KB	Output is correct
25	Correct	46 ms	6328 KB	Output is correct
26	Correct	103 ms	6328 KB	Output is correct
27	Incorrect	153 ms	6328 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

답안 #14913

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
0 / 37.0