oj.uz

답안 #404879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404879 2021-05-15T08:30:09 Z b00n0rp Simurgh (IOI17_simurgh) C++17
19 / 100
 185 ms 7096 KB 
#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;

#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pii>
#define F first
#define S second
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)

const int MX = 505;

int N;
vpii adj[MX];
vpii edges;
vi T;
vi ans;
int status[MX*MX];
bitset<MX> vis;
int dep[MX];
pii low[MX],par[MX];

void dfs(int u,int d){
	vis[u] = 1;
	dep[u] = d;
	for(auto v:adj[u]){
		if(vis[v.F] and dep[v.F] > d){
			low[u] = min(low[u],low[v.F]);
		}
		else if(vis[v.F]){
			low[u] = min(low[u],{dep[v.F],v.S});
		}
		else{
			T.pb(v.S);
			par[v.F] = {u,v.S};
			low[v.F] = {d,v.S};
			dfs(v.F,d+1);
		}
	}
}

int dsu_par[MX],dsu_rank[MX];

int find(int x){
	if(dsu_par[x] == x) return dsu_par[x];
	return dsu_par[x] = find(dsu_par[x]);
}

void merge(int u,int v){
	u = find(u);
	v = find(v);
	if(dsu_rank[u] < dsu_rank[v]) swap(u,v);
	dsu_par[v] = u;
	dsu_rank[u]++;
}

int count(vi gg){
	FOR(i,1,N+1){
		dsu_par[i] = i;
		dsu_rank[i] = 1;
	}
	for(auto x:gg) merge(edges[x].F,edges[x].S);
	int precount = 0;
	for(auto x:T){
		if(find(edges[x].F) != find(edges[x].S)){
			merge(edges[x].F,edges[x].S);
			gg.pb(x);
			precount += status[x];
		}
	}
	return count_common_roads(gg)-precount;
}

void solve(vi gg,int k){
	if(k == 0) return;
	if(gg.size() == k){
		for(auto x:gg){
			status[x] = 1;
		}
		return;
	}
	vi gg1,gg2;
	REP(i,gg.size()){
		if(i < gg.size()/2) gg1.pb(gg[i]);
		else gg2.pb(gg[i]);
	}
	int c = count(gg1);
	solve(gg1,c);
	solve(gg2,k-c);
}

vi find_roads(int n, vi u, vi v) {
	N = n;
	int m = u.size();
	REP(i,m){
		u[i]++;
		v[i]++;
		adj[u[i]].pb({v[i],i});
		adj[v[i]].pb({u[i],i});
		edges.pb({u[i],v[i]});
	}
	vis.reset();
	par[1] = {1,-1};
	low[1] = {0,-1};
	dfs(1,0);
	sort(T.begin(),T.end());
	REP(i,m) status[i] = -1;
	int basic = count_common_roads(T);
	FOR(i,1,n+1){
		if(low[i].S != -1 and (!binary_search(T.begin(),T.end(),low[i].S))){
			// cout << i << " " << low[i].F << " " << low[i].S << "\n";
			int cur = i;
			vi known;
			vi unknown;
			while(dep[cur] != low[i].F){
				if(status[par[cur].S] == -1) unknown.pb(par[cur].S);
				else known.pb(par[cur].S);
				cur = par[cur].F;
			}
			if(unknown.empty()) continue;
			if(known.empty()){
				vpii bruh;
				int mn = basic,mx = basic;
				for(auto y:unknown){
					vi gg;
					gg.pb(low[i].S);
					for(auto x:T){
						if(x != y) gg.pb(x);
					}
					bruh.pb({y,count_common_roads(gg)});
					mn = min(mn,bruh.back().S);
					mx = max(mx,bruh.back().S);
				}
				if(mn == mx){
					for(auto y:unknown) status[y] = 0;
				}
				else{
					for(auto y:bruh){
						if(y.S == mn) status[y.F] = 1;
						else status[y.F] = 0;
					}
				}
			}
			else{
				vi gg;
				gg.pb(low[i].S);
				for(auto x:T){
					if(x != known[0]) gg.pb(x);
				}
				int roy = count_common_roads(gg)-(basic-status[known[0]]);
				for(auto y:unknown){
					gg.clear();
					gg.pb(low[i].S);
					for(auto x:T){
						if(x != y) gg.pb(x);
					}
					status[y]  = basic-count_common_roads(gg)-roy;
				}
			}
		}
	}
	// cout << "yo\n";
	FOR(i,1,n+1){
		vi gg;
		for(auto x:adj[i]){
			if(x.F > i) gg.pb(x.S);
		}
		solve(gg,count(gg));
	}
	REP(i,m){
		if(status[i] == 1){
			ans.pb(i);
			// cout << i << "\n";
		}
	}
	return ans;
}

Compilation message

simurgh.cpp: In function 'void solve(std::vector<int>, int)':
simurgh.cpp:79:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |  if(gg.size() == k){
      |     ~~~~~~~~~~^~~~
simurgh.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,n) for(int i = 0; i < n; i ++)
......
   86 |  REP(i,gg.size()){
      |      ~~~~~~~~~~~                   
simurgh.cpp:86:2: note: in expansion of macro 'REP'
   86 |  REP(i,gg.size()){
      |  ^~~
simurgh.cpp:87:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   if(i < gg.size()/2) gg1.pb(gg[i]);
      |      ~~^~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB correct
2 Incorrect 13 ms 4948 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB correct
2 Incorrect 13 ms 4948 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB correct
2 Incorrect 13 ms 4948 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 113 ms 4988 KB correct
4 Correct 176 ms 6896 KB correct
5 Correct 182 ms 7008 KB correct
6 Correct 172 ms 6996 KB correct
7 Correct 113 ms 7020 KB correct
8 Correct 131 ms 6992 KB correct
9 Correct 173 ms 7028 KB correct
10 Correct 185 ms 6968 KB correct
11 Correct 184 ms 7096 KB correct
12 Correct 182 ms 6968 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 156 ms 6968 KB correct
15 Correct 179 ms 6968 KB correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB correct
2 Incorrect 13 ms 4948 KB WA in grader: NO
3 Halted 0 ms 0 KB -