글 읽기 - 메모리가 128MB를 초과하는 시점이 어디인지 궁금합니다.

portableangel 8년 전 2

kosaraju SCC + 2-SAT 코드입니다.

산술 계산으로는 70MB 이내인데 계속 터져나가서

250000 500000 랜덤 제너레이트 최대 입력을 넣었더니 110MB 내외에서 작동하는 것이 확인되었습니다.

이 코드가 128MB를 압도적으로 초과하게 만드는 입력이 있나요?

아니면 조금만 더 최적화하면 메모리 제한 내로 통과할 수 있을까요?

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <utility>

using namespace std;

typedef pair<int,int> ip;

class p {
public:
	int num, dfn;
	vector<p*> e, re;
};

bool cmp(const p* i, const p* j) {
	return i->dfn>j->dfn;
}

bool cmpn(const p* i, const p* j) {
	return i->num<j->num;
}

int n, m;
int dfn, sccn;
int sn[1000000];
bool visit[1000000];
vector<vector<int> > scc;
vector<vector<int> > con;
int ind[1000000], s[1000000];

void dfs(p* u) {
	visit[u->num]=true;
	for(int i=0;i<u->e.size();i++) {
		if(!visit[u->e[i]->num]) dfs(u->e[i]);
	}
	u->dfn=dfn++;
}

void dfsr(p* u) {
	visit[u->num]=true;
	scc[sccn].push_back(u->num);
	for(int i=0;i<u->re.size();i++) {
		if(!visit[u->re[i]->num]) dfsr(u->re[i]);
	}
}

p* list[1000000];
queue<int> q;
map<ip,bool> pick;

int main() {
	scanf("%d %d",&n,&m);
	for(int i=0;i<2*m;i++) {
		list[i]=new p;
		list[i]->num=i;
	}
	for(int i=0;i<n;i++) {
		int u, su, v, sv;
		scanf("%d %d %d %d",&u,&su,&v,&sv);
		u--; v--;
		int pu=2*u+su, nu=2*u+(su+1)%2;
		int pv=2*v+sv, nv=2*v+(sv+1)%2;
		if(!pick.count(ip(nu,pv))) {
			list[nu]->e.push_back(list[pv]);
			list[pv]->re.push_back(list[nu]);
			pick[ip(nu,pv)]=true;
		}
		if(!pick.count(ip(nv,pu))) {
			list[nv]->e.push_back(list[pu]);
			list[pu]->re.push_back(list[nv]);
			pick[ip(nv,pu)]=true;
		}
	}
	pick.clear();
	for(int i=0;i<2*m;i++) if(!visit[i])
		dfs(list[i]);
	sort(list,list+2*m,cmp);
	memset(visit,0,sizeof(visit));
	for(int i=0;i<2*m;i++) if(!visit[list[i]->num]) {
		scc.resize(sccn+1);
		dfsr(list[i]); sccn++;
	}
	for(int i=0;i<sccn;i++) {
		for(int j=0;j<scc[i].size();j++)
			sn[scc[i][j]]=i;
	}
	for(int i=0;i<2*m;i+=2) {
		if(sn[i]==sn[i+1]) {
			puts("IMPOSSIBLE");
			return 0;
		}
	}
	sort(list,list+2*m,cmpn);
	con.resize(sccn);
	memset(s,-1,sizeof(s));
	for(int i=0;i<sccn;i++) {
		for(int j=0;j<scc[i].size();j++) {
			for(int k=0;k<list[scc[i][j]]->e.size();k++) {
				int v=sn[list[scc[i][j]]->e[k]->num];
				if(i!=v && !pick.count(ip(i,v))) {
					con[i].push_back(v);
					ind[v]++;
					pick[ip(i,v)]=true;
				}
			}
		}
	}
	for(int i=0;i<sccn;i++) {
		if(ind[i]==0) {
			q.push(i);
			s[i]=0;
		}
	}
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		if(s[u]==0) {
			for(int i=0;i<scc[u].size();i++) {
				int v=scc[u][i];
				if(v%2==0) s[sn[v+1]]=1;
				else s[sn[v-1]]=1;
			}
		}
		for(int i=0;i<con[u].size();i++) {
			int v=con[u][i];
			ind[v]--;
			if(ind[v]==0) {
				if(s[v]<0) s[v]=0;
				q.push(v);
			}
		}
	}
	for(int i=0;i<2*m;i+=2) {
		if(s[sn[i]]) puts("0");
		else puts("1");
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리가 128MB를 초과하는 시점이 어디인지 궁금합니다.

portableangel 8년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말