제출 #793486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793486		farhan132	Simurgh (IOI17_simurgh)	C++17	100 / 100	188 ms	8152 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef double dd;
typedef pair<ll , ll> ii;
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert
#define mem(a , b) memset(a, b ,sizeof(a))

const ll N = 505;  
vector < ii > v[N];
vector < tuple < ll , ll, ll > > e, Nice;
ll n, col[N * N], par[N], vis[N], edge[N], deg[N], D[N];

void dfs(ll node, ll shit){
	vis[node] = 1;
	for(auto [u, i] : v[node]){
		if(!vis[u]){
			edge[u] = i;
			D[u] = D[node] + 1; 
			par[u] = node;
			Nice.pb({node, u, i});
			dfs(u, 1);
		}
	}
}

ll Norm = 0;

void dfs(ll node){
	vis[node] = 1;
	for(auto [u, i] : v[node]){
		if(!vis[u]){
			dfs(u);
		}else{
			if(D[u] > D[node] || D[u] + 1 == D[node]) continue;
			vector < ll > edges, extra;
			ll cur = node;
			while(cur != u){
				if(col[edge[cur]] == -1) edges.pb(edge[cur]);
				else extra.pb(edge[cur]);
				cur = par[cur];
			}
			if(edges.size()){
				vector < ii > val; val.pb({Norm, i});
				if(extra.size()){
					edges.pb(extra[0]);
				}
				for(auto x : edges){
					vector < ll > query;
					for(auto [_ , __, j] : Nice){
						if(j == x) query.pb(i);
						else query.pb(j);
					}
					val.pb({count_common_roads(query), x});
				}
				sort(val.begin(), val.end());
				if(val[0].ff == val.back().ff){
					if(extra.size()){
						for(auto [_, x] : val) col[x] = col[extra[0]];
					}else{
						for(auto [_, x] : val) col[x] = 0;
					}
					
				}else{
					for(auto [_ , x] : val){
						col[x] = (_ == val[0].ff);
					}
				}
			}
		}
	}
	return;
}

struct DSU{
    vector < int > par;
    void start(int n){
        par.resize(n + 1);
        for(int i = 0; i <= n; i++) par[i] = i;
    }
    int find(int a){
        if(a == par[a]) return a;
        return par[a] = find(par[a]);
    }
    void merge(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return;
        par[x] = y;
        return;
    }
};

ll plag(vector < tuple < ll , ll, ll > > E){
	DSU T; T.start(n);
	vector < ll > golden;
	for(auto [x, y, i] : E){
		T.merge(x, y);
		golden.pb(i);
	}
	ll S = 0;
	for(auto [x, y, i] : Nice){
		if(T.find(x) == T.find(y)) continue;
		T.merge(x, y);
		golden.pb(i);
		S += col[i];
	}
	return count_common_roads(golden) - S;
}


std::vector<int> find_roads(int _n, std::vector<int> _u, std::vector<int> _v) {
	n = _n;
	for(ll i = 0; i < _u.size(); i++){
		e.pb({_u[i], _v[i], i});
	}
	for(auto [x, y, i] : e){
		v[x].pb({y, i});
		v[y].pb({x, i});
	}
	mem(col, -1);
	mem(vis, 0);

	par[0] = -1; 
	D[0] = 0;
	dfs(0, 1);

	vector < ll > golden;
	for(auto [x, y, i] : Nice){
		golden.pb(i);
	}
	Norm = count_common_roads(golden);
	mem(vis, 0);
	dfs(0);
	ll Sum = 0;

	for(auto [x, y, i] : Nice){
		if(col[i] == -1){
			col[i] = 1;
		}
		Sum += col[i];
	}
	assert(Norm == Sum);

	queue < ll > q;

	for(ll i = 0; i < n; i++){
		vector < tuple < ll , ll , ll > > dump;
		for(auto [u, j] : v[i]){
			dump.pb({i, u, j});
		}
		deg[i] = plag(dump);
		if(deg[i] == 1) q.push(i);
	}
	vector < ll > royal;
	mem(vis, 0);

	for(ll itr = 0; itr < n - 1; itr++){
		ll node = q.front(); q.pop();
		vis[node] = 1;
		vector < tuple < ll , ll , ll > > E;
		for(auto [u, i] : v[node]){
			if(vis[u] == 1) continue; 
			E.push_back({node, u, i});
		}
		ll l = 0, r = E.size() - 1, k = 0;
		while(l <= r){
			ll m = (l + r) / 2;
			vector < tuple < ll , ll , ll > > dump;
			for(ll i = 0; i <= m; i++) dump.pb(E[i]);
			if(plag(dump)){
				k = m;
				r = m - 1;
			}else{
				l = m + 1;
			}
		}
		auto [_, nxt, i] = E[k];
		royal.pb(i);
		deg[nxt]--;
		//cout << node << ' ' << nxt << '\n';
		if(deg[nxt] == 1) q.push(nxt);
	}

	return royal;
}

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:121:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |  for(ll i = 0; i < _u.size(); i++){
      |                ~~^~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30