oj.uz

Submission #366148

# Submission time Handle Problem Language Result Execution time Memory
366148 2021-02-13T10:59:40 Z Hemimor Restore Array (RMI19_restore) C++14
20 / 100
 600 ms 1004 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <random>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[8]={-1,0,1,0,1,1,-1,-1},dy[8]={0,1,0,-1,1,-1,1,-1};

vi vin(int n,int d=0){
	vi a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
		a[i]-=d;
	}
	return a;
}

vl vlin(int n,int d=0){
	vl a(n);
	for(auto &i:a){
		cin>>i;
		i-=d;
	}
	return a;
}

vvi vvin(int n,int m){
	vvi a(n,vi(m));
	for(int i=0;i<n;i++) for(auto &j:a[i]) cin>>j;
	return a;
}

vvi gin(int n,int m,int d=1){
	vvi g(n);
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		u-=d,v-=d;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	return g;
}

void vout(vi a){
	int n=a.size();
	cout<<n<<" :";
	for(auto i:a) cout<<' '<<i;
	cout<<endl;
}

void vvout(vvi a){
	int n=a.size();
	for(int i=0;i<n;i++) vout(a[i]);
}

bool ingrid(int x,int y,int n,int m){
	return 0<=x&&x<n&&0<=y&&y<m;
}

int n,m;

int main(){
	scanf("%d%d",&n,&m);
	vvp g(n+1);
	vi d(n+1,inf);
	d[0]=0;
	for(int i=0;i<n;i++){
		g[i].emplace_back(i+1,1);
		g[i+1].emplace_back(i,0);
	}
	for(int i=0;i<m;i++){
		int l,r,k,v;
		scanf("%d%d%d%d",&l,&r,&k,&v);
		r++;
		if(v==0){
			// A_r-A_l<=r-l-k
			g[l].emplace_back(r,r-l-k);
		}
		else{
			// A_r-A_l>=r-l-k+1
			// A_l-A_r<=l-r+k-1
			g[r].emplace_back(l,l-r+k-1);
		}
	}
	for(int i=0;i<=n;i++){
		bool B=0;
		for(int j=0;j<=n;j++){
			for(auto p:g[j]){
				int v=p.first;
				if(d[j]+p.second<d[v]){
					d[v]=d[j]+p.second;
					B=1;
				}
			}
		}
		if(B==1&&i==n){
			printf("-1\n");
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		if(i>1) printf(" ");
		printf("%d",d[i]-d[i-1]);
	}
	puts("");
}

Compilation message

restore.cpp: In function 'int main()':
restore.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
restore.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |   scanf("%d%d%d%d",&l,&r,&k,&v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 748 KB Output is correct
2 Correct 324 ms 856 KB Output is correct
3 Correct 350 ms 856 KB Output is correct
4 Correct 320 ms 876 KB Output is correct
5 Correct 556 ms 876 KB Output is correct
6 Correct 490 ms 876 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 748 KB Output is correct
2 Correct 324 ms 856 KB Output is correct
3 Correct 350 ms 856 KB Output is correct
4 Correct 320 ms 876 KB Output is correct
5 Correct 556 ms 876 KB Output is correct
6 Correct 490 ms 876 KB Output is correct
7 Correct 382 ms 880 KB Output is correct
8 Correct 368 ms 1004 KB Output is correct
9 Correct 365 ms 780 KB Output is correct
10 Correct 356 ms 876 KB Output is correct
11 Execution timed out 640 ms 868 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 359 ms 748 KB Output is correct
12 Correct 324 ms 856 KB Output is correct
13 Correct 350 ms 856 KB Output is correct
14 Correct 320 ms 876 KB Output is correct
15 Correct 556 ms 876 KB Output is correct
16 Correct 490 ms 876 KB Output is correct
17 Correct 382 ms 880 KB Output is correct
18 Correct 368 ms 1004 KB Output is correct
19 Correct 365 ms 780 KB Output is correct
20 Correct 356 ms 876 KB Output is correct
21 Execution timed out 640 ms 868 KB Time limit exceeded
22 Halted 0 ms 0 KB -