oj.uz

답안 #881848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881848 2023-12-02T04:21:50 Z djs100201 수천개의 섬 (IOI22_islands) C++17
0 / 100
 1000 ms 239880 KB 
#include "islands.h"
#include <variant>
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 2e5 + 505, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
vector<P>rev[n_];
ll prob[n_],out[n_],checked[n_];
set<P>v[n_],edge[n_];
P To[n_];
variant<bool, std::vector<int>>find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
	n=N,m=M;
    for(int i=0;i<m;i++){
		out[U[i]]++;
		v[U[i]].insert({V[i],i});
		rev[V[i]].push_back({U[i],i});
	}
	fill(prob,prob+n+1,1);
	//가능성이 존재한다.
	queue<ll>q;
	for(int i=0;i<n;i++){
		if(v[i].size())continue;
		q.push(i);
	}
	while(q.size()){
		a=q.front();
		q.pop();
		prob[a]=0;
		for(auto nxt:rev[a]){
			v[nxt.first].erase(nxt);
			if(v[nxt.first].size()==0){
				q.push(nxt.first);
			}
		}
	}
	ll now=0;
	vector<int>ret,ret_rev;
	while(1){
		if(!v[now].size())return false;
		if(v[now].size()==1){
			ret.push_back((*v[now].begin()).second);
			ret_rev.push_back((*v[now].begin()).second);
			queue<ll>q;
			for(auto nxt:rev[now]){
				v[nxt.first].erase(nxt);
				if(v[nxt.first].size()==0)q.push(nxt.first);
			}
			while(q.size()){
				x=q.front();
				q.pop();
				for(auto nxt:rev[x]){
					v[nxt.first].erase(nxt);
					if(v[nxt.first].size()==0)q.push(nxt.first);
				}
			}
			out[now]=0;
			now=(*v[now].begin()).first;
		}
		else{
			
			for(int i=0;i<n;i++){
				if(i==now || !v[i].size())continue;
				auto cur=*v[i].begin();
				//v[i].clear();
				edge[i].insert(cur);
				//cout<<i<<' '<<cur.first<<' '<<cur.second<<endl;
				//v[i].insert(a);
			}
			auto a=*v[now].begin();
			//cout<<a<<' '<<b<<endl;
			x=now;
			edge[now].clear();
			edge[now].insert(a);
			for(int i=0;i<n;i++)To[i]={-1,-1};
			while(1){
				P nxt;
				//cout<<x<<endl;
				if(edge[x].size()==1){
					nxt=*edge[x].begin();
				}
				else{
					for(auto i:edge[x]){
						if(i!=To[x])nxt=i;
					}
				}
				To[nxt.first]={x,nxt.second};
				//cout<<x<<' '<<nxt.first<<' '<<nxt.second<<endl;
				edge[nxt.first].insert({x,nxt.second});
				edge[x].erase(nxt);
				ret.push_back(nxt.second);
				x=nxt.first;
				if(x==now)break;
			}
			edge[now].clear();
			auto it=v[now].end();
			it--;
			//cout<<a<<' '<<b<<endl;
			x=now;
			edge[now].insert(*it);
			for(int i=0;i<n;i++)To[i]={-1,-1};
			base=0;
			while(1){
				P nxt;
				//cout<<x<<endl;
				if(edge[x].size()==1){
					nxt=*edge[x].begin();
				}
				else{
					for(auto i:edge[x]){
						if(i!=To[x])nxt=i;
					}
				}
				To[nxt.first]={x,nxt.second};
				//cout<<x<<' '<<nxt.first<<' '<<nxt.second<<endl;
				edge[nxt.first].insert({x,nxt.second});
				edge[x].erase(nxt);
				ret.push_back(nxt.second);
				x=nxt.first;
				if(x==now)break;
			}
			a=*v[now].begin();
			//cout<<a<<' '<<b<<endl;
			x=now;
			edge[now].clear();
			edge[now].insert(a);
			for(int i=0;i<n;i++)To[i]={-1,-1};
			while(1){
				P nxt;
				//cout<<x<<endl;
				if(edge[x].size()==1){
					nxt=*edge[x].begin();
				}
				else{
					for(auto i:edge[x]){
						if(i!=To[x])nxt=i;
					}
				}
				To[nxt.first]={x,nxt.second};
				//cout<<x<<' '<<nxt.first<<' '<<nxt.second<<endl;
				edge[nxt.first].insert({x,nxt.second});
				edge[x].erase(nxt);
				ret.push_back(nxt.second);
				x=nxt.first;
				if(x==now)break;
			}
			edge[now].clear();
			it=v[now].end();
			it--;
			//cout<<a<<' '<<b<<endl;
			x=now;
			edge[now].insert(*it);
			for(int i=0;i<n;i++)To[i]={-1,-1};
			base=0;
			while(1){
				P nxt;
				//cout<<x<<endl;
				if(edge[x].size()==1){
					nxt=*edge[x].begin();
				}
				else{
					for(auto i:edge[x]){
						if(i!=To[x])nxt=i;
					}
				}
				To[nxt.first]={x,nxt.second};
				//cout<<x<<' '<<nxt.first<<' '<<nxt.second<<endl;
				edge[nxt.first].insert({x,nxt.second});
				edge[x].erase(nxt);
				ret.push_back(nxt.second);
				x=nxt.first;
				if(x==now)break;
			}
			break;
		}
	}
	reverse(all(ret_rev));
	for(auto i:ret_rev)ret.push_back(i);
    return ret;
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 29528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 6 ms 29532 KB Output is partially correct
2 Execution timed out 1095 ms 239880 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 7 ms 30040 KB Output is partially correct
2 Execution timed out 1050 ms 228800 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 29532 KB Output is partially correct
2 Partially correct 7 ms 29788 KB Output is partially correct
3 Partially correct 80 ms 46676 KB Output is partially correct
4 Partially correct 72 ms 47324 KB Output is partially correct
5 Partially correct 8 ms 30044 KB Output is partially correct
6 Partially correct 7 ms 29940 KB Output is partially correct
7 Partially correct 5 ms 29532 KB Output is partially correct
8 Correct 6 ms 29532 KB Output is correct
9 Correct 5 ms 29532 KB Output is correct
10 Correct 8 ms 29992 KB Output is correct
11 Incorrect 8 ms 30112 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 29528 KB Output isn't correct
2 Halted 0 ms 0 KB -