Submission #3221854


Source Code Expand

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int x; SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long x; SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
////////////////////////////////////////////////////////////////////
typedef pair<ll,ll> PLL;
typedef pair<PLL,PLL> PLLL;

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size,-1) { }

    int root(int x){
        if (data[x] < 0) return x;
        else return data[x] = root(data[x]);
    }

    int size(int x){
        return -data[root(x)];
    }

    bool isConnect(int x,int y){
        return root(x) == root(y);
    }

    bool connect(int x , int y){
        x = root(x);
	    y = root(y);
	
        if(x==y) return false;
        
        if(data[x] > data[y]){
            x ^= y;
            y ^= x;
            x ^= y;
        }
        
        data[x] = data[x] + data[y]; // membersize++
        data[y] = x;
        return true;
    }
};

UnionFind U(10002);

int main(){

	ll ans = 0;
	int H,W; SCD2(H,W);
	int Sx,Sy; SCD2(Sx,Sy);
	int Gx,Gy; SCD2(Gx,Gy);

	int dx[4] = {0,1,0,-1};
	int dy[4] = {1,0,-1,0};

	static ll P[102][102] = {};
	FORq(j,1,H){
		FORq(i,1,W){
			SCD(P[i][j]);
			ans += P[i][j];
		}
	}

	int selected = 0;

	priority_queue<pair<ll,PLLL> >Q;
	FORq(j,1,H){
		FORq(i,1,W){
			PII start = MP(i,j);
			PII endd = MP(i+1,j);
			ll cost = P[i][j] * P[i+1][j];
			Q.push(MP(cost,MP(start,endd)));

			endd = MP(i,j+1);
			cost = P[i][j] * P[i][j+1];
			Q.push(MP(cost,MP(start,endd)));
		}
	}

	while((selected <= W*H-2) and (!Q.empty())){
		pair<ll,PLLL> now = Q.top(); Q.pop();
		ll ncost = now.first;
		PLL A = now.second.first;
		PLL B = now.second.second;
		int a =  W * (A.second - 1) + (A.first);
		int b =  W * (B.second - 1) + (B.first);
		
		if (U.isConnect(a,b) == false) {
			U.connect(a,b);
			selected++;
			ans += ncost;
		}
	}

	PRINTLLD(ans);

}

Submission Info

Submission Time
Task D - Game on a Grid
User Lithium
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2895 Byte
Status RE
Exec Time 119 ms
Memory 1784 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:6:29: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘ll* {aka long long int*}’ [-Wformat=]
 #define SCD(n) scanf("%d",&n)
                             ^
./Main.cpp:85:4: note: in expansion of macro ‘SCD’
    SCD(P[i][j]);
    ^
./Main.cpp:75:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int H,W; SCD2(H,W);
                    ^
./Main.cpp:76:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int Sx,Sy; SCD2(Sx,Sy);
                        ^
./Main.cpp:77:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int Gx,Gy; SCD2(Gx,Gy);
                        ^
./Main.cpp:85:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wu...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 3
AC × 19
RE × 13
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask0_sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt RE 119 ms 1784 KB
subtask1_08.txt RE 103 ms 1784 KB
subtask1_09.txt RE 103 ms 1784 KB
subtask1_10.txt RE 103 ms 1784 KB
subtask1_11.txt RE 103 ms 1784 KB
subtask1_12.txt RE 103 ms 1784 KB
subtask1_13.txt RE 102 ms 1784 KB
subtask1_14.txt RE 102 ms 1784 KB
subtask1_15.txt RE 103 ms 1784 KB
subtask1_16.txt AC 6 ms 1784 KB
subtask1_17.txt AC 1 ms 384 KB
subtask1_18.txt AC 1 ms 384 KB
subtask1_19.txt AC 1 ms 384 KB
subtask1_20.txt RE 103 ms 1784 KB
subtask1_21.txt RE 103 ms 1784 KB
subtask1_22.txt RE 103 ms 1784 KB
subtask1_23.txt RE 104 ms 1784 KB
subtask1_24.txt AC 1 ms 256 KB
subtask1_25.txt AC 1 ms 256 KB
subtask1_26.txt AC 1 ms 384 KB
subtask1_27.txt AC 1 ms 256 KB
subtask1_28.txt AC 1 ms 384 KB
subtask1_29.txt AC 1 ms 256 KB