oj.uz

Submission #99319

# Submission time Handle Problem Language Result Execution time Memory
99319 2019-03-02T12:20:04 Z TadijaSebez Arranging Tickets (JOI17_arranging_tickets) C++11
10 / 100
 1712 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200050;
const int M=2*N;
const int inf=1e9+7;
int ls[M],rs[M],tsz,root,lzy[M],mx[M];
void Add(int &c, int ss, int se, int qs, int qe, int f)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(!c) c=++tsz;
	if(qs<=ss && qe>=se){ lzy[c]+=f;mx[c]+=f;return;}
	int mid=ss+se>>1;
	Add(ls[c],ss,mid,qs,qe,f);
	Add(rs[c],mid+1,se,qs,qe,f);
	mx[c]=max(mx[ls[c]],mx[rs[c]])+lzy[c];
}
int Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return -inf;
	if(qs<=ss && qe>=se) return mx[c];
	int mid=ss+se>>1;
	return max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe))+lzy[c];
}
void init()
{
	for(int i=1;i<=tsz;i++) ls[i]=rs[i]=lzy[i]=mx[i]=0;
	tsz=root=0;
}
int a[N],b[N],c[N],n,m;
ll Solve()
{
	init();
	int i;
	ll ans=0;
	for(i=1;i<=m;i++)
	{
		ans+=c[i]/2;
		if(a[i]>b[i]) swap(a[i],b[i]);
		if(c[i]&1) Add(root,1,n,a[i],b[i]-1,1);
	}
	for(i=1;i<=m;i++) if(c[i]&1)
	{
		int pre=mx[root],nxt=max(Get(root,1,n,1,a[i]-1),Get(root,1,n,b[i],n))+1;
		if(pre>nxt) Add(root,1,n,1,n,1),Add(root,1,n,a[i],b[i]-1,-2);
	}
	ans+=mx[root];
	return ans;
}
ll Brute()
{
	ll sum=0,ans=inf;
	for(int i=1;i<=m;i++){ if(a[i]>b[i]) swap(a[i],b[i]);sum+=c[i]/2;}
	for(int mask=0;mask<(1<<m);mask++)
	{
		init();
		for(int i=1;i<=m;i++) if(c[i]&1)
		{
			if((mask>>(i-1))&1)
			{
				Add(root,1,n,a[i],b[i]-1,1);
			}
			else
			{
				Add(root,1,n,1,n,1);
				Add(root,1,n,a[i],b[i]-1,-1);
			}
		}
		ans=min(ans,(ll)mx[root]);
	}
	return sum+ans;
}
void input()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=m;i++) scanf("%i %i %i",&a[i],&b[i],&c[i]);
}
void Test()
{
    srand(time(0));
    int t=10000;
    for(int i=1;i<=t;i++)
	{
		n=rand()%3+2;
		m=rand()%5+1;
		for(int j=1;j<=m;j++)
		{
			do
			{
				a[j]=rand()%n+1;
				b[j]=rand()%n+1;
			}while(a[j]==b[j]);
			c[j]=rand()%100+1;
		}
		ll sol=Solve();
		ll bru=Brute();
		if(sol!=bru)
		{
			printf("%i %i\n",n,m);
			for(int j=1;j<=m;j++) printf("%i %i %i\n",a[j],b[j],c[j]);
			printf("Solve: %lld\n",sol);
			printf("Brute: %lld\n",bru);
			return;
		}
		printf("%i OK\n",i);
	}
}
int main()
{
	//Test();
	input();
	printf("%lld\n",Brute());
	return 0;
}

Compilation message

arranging_tickets.cpp: In function 'void input()':
arranging_tickets.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
arranging_tickets.cpp:76:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i %i %i",&a[i],&b[i],&c[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1712 ms 504 KB Output is correct
2 Correct 1364 ms 384 KB Output is correct
3 Correct 1499 ms 476 KB Output is correct
4 Correct 1571 ms 504 KB Output is correct
5 Correct 1495 ms 504 KB Output is correct
6 Correct 1565 ms 412 KB Output is correct
7 Correct 1334 ms 504 KB Output is correct
8 Correct 1247 ms 416 KB Output is correct
9 Correct 1560 ms 504 KB Output is correct
10 Correct 1500 ms 504 KB Output is correct
11 Correct 1452 ms 384 KB Output is correct
12 Correct 1418 ms 384 KB Output is correct
13 Correct 1447 ms 504 KB Output is correct
14 Correct 1534 ms 384 KB Output is correct
15 Correct 1346 ms 416 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1712 ms 504 KB Output is correct
2 Correct 1364 ms 384 KB Output is correct
3 Correct 1499 ms 476 KB Output is correct
4 Correct 1571 ms 504 KB Output is correct
5 Correct 1495 ms 504 KB Output is correct
6 Correct 1565 ms 412 KB Output is correct
7 Correct 1334 ms 504 KB Output is correct
8 Correct 1247 ms 416 KB Output is correct
9 Correct 1560 ms 504 KB Output is correct
10 Correct 1500 ms 504 KB Output is correct
11 Correct 1452 ms 384 KB Output is correct
12 Correct 1418 ms 384 KB Output is correct
13 Correct 1447 ms 504 KB Output is correct
14 Correct 1534 ms 384 KB Output is correct
15 Correct 1346 ms 416 KB Output is correct
16 Incorrect 231 ms 420 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1712 ms 504 KB Output is correct
2 Correct 1364 ms 384 KB Output is correct
3 Correct 1499 ms 476 KB Output is correct
4 Correct 1571 ms 504 KB Output is correct
5 Correct 1495 ms 504 KB Output is correct
6 Correct 1565 ms 412 KB Output is correct
7 Correct 1334 ms 504 KB Output is correct
8 Correct 1247 ms 416 KB Output is correct
9 Correct 1560 ms 504 KB Output is correct
10 Correct 1500 ms 504 KB Output is correct
11 Correct 1452 ms 384 KB Output is correct
12 Correct 1418 ms 384 KB Output is correct
13 Correct 1447 ms 504 KB Output is correct
14 Correct 1534 ms 384 KB Output is correct
15 Correct 1346 ms 416 KB Output is correct
16 Incorrect 231 ms 420 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1712 ms 504 KB Output is correct
2 Correct 1364 ms 384 KB Output is correct
3 Correct 1499 ms 476 KB Output is correct
4 Correct 1571 ms 504 KB Output is correct
5 Correct 1495 ms 504 KB Output is correct
6 Correct 1565 ms 412 KB Output is correct
7 Correct 1334 ms 504 KB Output is correct
8 Correct 1247 ms 416 KB Output is correct
9 Correct 1560 ms 504 KB Output is correct
10 Correct 1500 ms 504 KB Output is correct
11 Correct 1452 ms 384 KB Output is correct
12 Correct 1418 ms 384 KB Output is correct
13 Correct 1447 ms 504 KB Output is correct
14 Correct 1534 ms 384 KB Output is correct
15 Correct 1346 ms 416 KB Output is correct
16 Incorrect 231 ms 420 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1712 ms 504 KB Output is correct
2 Correct 1364 ms 384 KB Output is correct
3 Correct 1499 ms 476 KB Output is correct
4 Correct 1571 ms 504 KB Output is correct
5 Correct 1495 ms 504 KB Output is correct
6 Correct 1565 ms 412 KB Output is correct
7 Correct 1334 ms 504 KB Output is correct
8 Correct 1247 ms 416 KB Output is correct
9 Correct 1560 ms 504 KB Output is correct
10 Correct 1500 ms 504 KB Output is correct
11 Correct 1452 ms 384 KB Output is correct
12 Correct 1418 ms 384 KB Output is correct
13 Correct 1447 ms 504 KB Output is correct
14 Correct 1534 ms 384 KB Output is correct
15 Correct 1346 ms 416 KB Output is correct
16 Incorrect 231 ms 420 KB Output isn't correct
17 Halted 0 ms 0 KB -