답안 #69967 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69967	2018-08-22T07:12:02 Z	WA_TLE	낙하산 고리들 (IOI12_rings)	C++14	37 / 100	1502 ms	94636 KB

rings

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000000;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

vector<vector<int>>len;
vector<int>cri;//Tじの候補
vector<int>uni[4];
vector<int>ran[4];
int rop[4]={0};//その状態でのループ数
int geans;
int Taru=0;
void Init(int n){
	len.res(n);
	geans=n;
	cri.pub(0x869120);cri.pub(-1);cri.pub(-1);cri.pub(-1);
	for(int j=0;j<4;j++){
		ran[j].res(n);uni[j].res(n);
		for(int i=0;i<n;i++){ran[j][i]=1;uni[j][i]=i;}
	}
}
int en=-1;
int sta;
vector<int>dfit;
vector<int>hai;
vector<pair<int,int>>queri;
bool unfi(int A,int B,int bas){
	if(cri[bas]==A||cri[bas]==B){return false;}
	int a=A,b=B;
	while(a!=uni[bas][a]){a=uni[bas][a];}
	while(b!=uni[bas][b]){b=uni[bas][b];}
	if(ran[bas][a]<ran[bas][b]){swap(a,b);}
	uni[bas][b]=a;
	if(a==b){rop[bas]++;}
	else{ran[bas][a]+=ran[bas][b];}
	return (a==b);
}
void reki(int bas){
	for(int i=0;i<len.size();i++){uni[bas][i]=i;ran[bas][i]=1;}
	for(auto it:queri){unfi(it.fir,it.sec,bas);}
}
void Link(int A,int B){
	
	len[A].pub(B);
	len[B].pub(A);
	if(Taru){
		if(len[A].size()==3){
			for(auto &it:cri){
				if(it!=A&&it!=len[A][0]&&it!=len[A][1]&&it!=len[A][2]){it=-1;}
			}
		}
		if(len[A].size()>3){
			for(auto &it:cri){if(it!=A){it=-1;}}
		}
	}else if(len[A].size()==3){
		Taru=1;
		cri.clear();
		cri.pub(A);reki(0);
		cri.pub(len[A][0]);reki(1);
		cri.pub(len[A][1]);reki(2);
		cri.pub(len[A][2]);reki(3);
	}
	if(Taru){
		if(len[B].size()==3){
			for(auto &it:cri){
				if(it!=B&&it!=len[B][0]&&it!=len[B][1]&&it!=len[B][2]){it=-1;}
			}
		}
		if(len[B].size()>3){
			for(auto &it:cri){if(it!=B){it=-1;}}
		}
	}else if(len[B].size()==3){
		Taru=1;
		cri.clear();
		cri.pub(B);reki(0);//構築する
		cri.pub(len[B][0]);reki(1);
		cri.pub(len[B][1]);reki(2);
		cri.pub(len[B][2]);reki(3);
	}
	queri.pub(mp(A,B));
	if(Taru){geans=0;}
	for(int j=0;j<4;j++){
		if(cri[j]==-1){continue;}
		bool ret=unfi(A,B,j);
		if((!Taru)&&ret&&rop[j]==1){
			int a=A;
			while(a!=uni[j][a]){a=uni[j][a];}
			geans=ran[j][a];
		}
		if((!Taru)&&rop[j]==2){geans=0;}
		if(Taru&&rop[j]>0){cri[j]=-1;}
		if(Taru&&rop[j]==0){geans++;}
	}
}
int CountCritical(void){return geans;}

Compilation message

rings.cpp: In function 'void reki(int)':
rings.cpp:87:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<len.size();i++){uni[bas][i]=i;ran[bas][i]=1;}
              ~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	428 ms	49452 KB	Output is correct
2	Correct	1091 ms	75800 KB	Output is correct
3	Correct	983 ms	90144 KB	Output is correct
4	Correct	1271 ms	94636 KB	Output is correct
5	Correct	1264 ms	94636 KB	Output is correct
6	Correct	1230 ms	94636 KB	Output is correct
7	Correct	895 ms	94636 KB	Output is correct
8	Correct	1370 ms	94636 KB	Output is correct
9	Correct	1502 ms	94636 KB	Output is correct
10	Correct	840 ms	94636 KB	Output is correct

Subtask #3
0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	5 ms	884 KB	Output is correct
3	Correct	4 ms	1028 KB	Output is correct
4	Correct	2 ms	1028 KB	Output is correct
5	Correct	3 ms	1028 KB	Output is correct
6	Correct	5 ms	1124 KB	Output is correct
7	Correct	2 ms	1124 KB	Output is correct
8	Correct	4 ms	1124 KB	Output is correct
9	Correct	5 ms	1124 KB	Output is correct
10	Correct	5 ms	1124 KB	Output is correct
11	Correct	5 ms	94636 KB	Output is correct
12	Incorrect	8 ms	94636 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	5 ms	884 KB	Output is correct
3	Correct	4 ms	1028 KB	Output is correct
4	Correct	2 ms	1028 KB	Output is correct
5	Correct	3 ms	1028 KB	Output is correct
6	Correct	5 ms	1124 KB	Output is correct
7	Correct	2 ms	1124 KB	Output is correct
8	Correct	4 ms	1124 KB	Output is correct
9	Correct	5 ms	1124 KB	Output is correct
10	Correct	5 ms	1124 KB	Output is correct
11	Correct	5 ms	94636 KB	Output is correct
12	Incorrect	8 ms	94636 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5
0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	5 ms	884 KB	Output is correct
3	Correct	4 ms	1028 KB	Output is correct
4	Correct	2 ms	1028 KB	Output is correct
5	Correct	3 ms	1028 KB	Output is correct
6	Correct	5 ms	1124 KB	Output is correct
7	Correct	2 ms	1124 KB	Output is correct
8	Correct	4 ms	1124 KB	Output is correct
9	Correct	5 ms	1124 KB	Output is correct
10	Correct	5 ms	1124 KB	Output is correct
11	Correct	428 ms	49452 KB	Output is correct
12	Correct	1091 ms	75800 KB	Output is correct
13	Correct	983 ms	90144 KB	Output is correct
14	Correct	1271 ms	94636 KB	Output is correct
15	Correct	1264 ms	94636 KB	Output is correct
16	Correct	1230 ms	94636 KB	Output is correct
17	Correct	895 ms	94636 KB	Output is correct
18	Correct	1370 ms	94636 KB	Output is correct
19	Correct	1502 ms	94636 KB	Output is correct
20	Correct	840 ms	94636 KB	Output is correct
21	Correct	5 ms	94636 KB	Output is correct
22	Incorrect	8 ms	94636 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

답안 #69967

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 0 / 18.0

Subtask #4 0 / 14.0

Subtask #5 0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
0 / 18.0

Subtask #4
0 / 14.0

Subtask #5
0 / 31.0