| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1055341 |
2024-08-12T17:41:39 Z |
ReLice |
Simurgh (IOI17_simurgh) |
C++17 |
|
0 ms |
348 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
#define ll int
#define ins insert
#define pb push_back
#define pf push_front
#define pob pop_badk()
#define pof pop_front()
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;
template<class S,class T>
bool chmin(S &a,const T &b) {
return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
return a<b?(a=b)==b:false;
}
const ll N = 5e2 + 7;
const ll M = N * N;
vector<pll> g(N);
vll u, v;
ll n, m;
ll p[N], d[N];
ll vis[M];
ll royal[M];
ll ct;
pair<ll,ll> mx[N];
ll pr(ll a, ll ed){
if(a == v[ed]) return u[ed];
if(a == u[ed]) return v[ed];
return -1;
}
ll pr(ll a){return pr(a, p[a]); }
void build_tree(ll v){
mx[v] = {d[v], -1};
//~ cout<<v<<endl;
for(auto [to, r] : g[v]){
if(r == p[v])continue;
if(d[to] != d[n]) {
mx[v] = min(mx[v], {d[to], r});
continue;
}
d[to] = d[v] + 1;
p[to] = r;
build_tree(to);
mx[v] = min(mx[v], mx[to]);
}
}
ll check(ll v, ll top){
while(pr(v) != top){
v = pr(v);
}
if(vis[p[v]]) return 2;
return 1;
}
vll get_path(ll v, ll top){
vll path;
while(v != top){
path.pb(v);
v = pr(v);
}
reverse(all(path));
return path;
}
vll get_init(){
vll v(n - 1);
for(ll i=1;i<n;i++){
v[i - 1] = p[i];
}
return v;
}
void tp1(ll u, ll ed){// if don't know any edges
ll i;
ll top = pr(u, ed);
vll v = get_init();
vll path = get_path(u, top);
vll res;
ll mn = ct, mx = ct;
for(auto i : path){
v[i - 1] = ed;
ll x = count_common_roads(v);
res.pb(x);
mx = max(mx, x);
mn = min(mn, x);
v[i - 1] = p[i];
}
for(i=0;i<(ll)res.size();i++){
ll a = path[i];
vis[p[a]] = 1;
if(res[i] == mx){
royal[p[a]] = 0;
}
else royal[p[a]] = 1;
}
vis[ed] = 1;
if (ct == mx){
royal[ed] = 0;
}else royal[ed] = 1;
}
void tp2(ll u, ll ed){// if we know some edges
if(vis[p[u]]) return;
ll top = pr(u, ed);
vll v = get_init();
vll path = get_path(u, top);
top = path[0];
v[top - 1] = ed;
ll x = count_common_roads(v);
v[top - 1] = p[top];
vis[ed] = 1;
royal[ed] = x - ( ct - royal[p[top]] );
for(auto i : path){
if(vis[p[i]]) continue;
vis[p[i]] = 1;
v[i - 1] = ed;
ll x = count_common_roads(v);
v[i - 1] = p[i];
// x = ct - royal[i] + royal[ed]
// royal[i] = ct - x + royal[ed]
vis[p[i]] = 1;
royal[p[i]] = ct - x + royal[ed];
}
}
void calc(ll v){
for(auto [to, r] : g[v]){
if(d[to] <= d[v]) continue;
calc(to);
}
if(mx[v].sc == -1){
if(p[v] >= 0){
vis[p[v]] = 1;
royal[p[v]] = 1;
}
return;
}
ll top = pr(v, mx[v].sc);
if(top >= 0 && d[top] < d[v]){
if(check(v, top) == 1) tp1(v, mx[v].sc);
else tp2(v, mx[v].sc);
}
}
void calc_tree(){
memset(d, 0x3f, sizeof(d));
p[0] = -1;
d[0] = 0;
build_tree(0);
ct = count_common_roads(get_init());
calc(0);
}
ll count(deque<ll> &ed, vll &v, ll m, ll u){
ll cur = ct;
for(ll i=0;i<m;i++){
ll a = pr(u, ed[i]);
cur -= royal[p[a]];
v[a - 1] = ed[i];
}
ll x = count_common_roads(v);
for(ll i=0;i<m;i++){
ll a = pr(u, ed[i]);
v[a - 1] = p[a];
}
return x - cur;
}
void find_others(ll u){
vll v = get_init();
deque<ll> ed;
for(auto [to, r] : g[u]){
if(vis[r]) continue;
vis[r] = 1;
ed.pb(r);
}
ll x = count(ed, v, (ll)ed.size(), u);
//~ cout<<u<<'*'<<x<<endl;
//~ for(auto i : ed) cout<<u<<' '<<pr(u, i)<<endl;
//~ cout<<endl;
for(ll i=1;i<=x;i++){
ll l = 0, r = (ll)ed.size();
while(l + 1 < r){
ll m = (l + r) / 2;
if(count(ed, v, (ll)ed.size(), u) == 0) l = m;
else r = m;
}
royal[ed[r-1]] = 1;
while(r--) ed.pof;
}
for(auto [to, r] : g[u]){
if(pr(to) != u) continue;
find_others(to);
}
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
ll i;
m = U.sz;
n = N, u = U, v = V;
for(i=0;i<m;i++){
g[u[i]].pb({v[i],i});
g[v[i]].pb({u[i],i});
}
calc_tree();
//~ for(ll i=0;i<m;i++)if(vis[i])cout<<i<<' '<<royal[i]<<endl;
find_others(0);
//~ for(i=1;i<n;i++)cout<<u[p[i]]<<' '<<v[p[i]]<<endl;
vll v;
for(i=0;i<m;i++){
//~ if(vis[i])cout<<i<<' '<<royal[i]<<endl;
if(royal[i])v.pb(i);
}
return v;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
correct |
| 2 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
