| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 721513 | minhcool | Simurgh (IOI17_simurgh) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define save savee
#define find findd
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 505 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, m, a[N];
int count(vector<int> v){
if((double)clock() / (double)CLOCKS_PER_SEC >= 1.0)) exit(0);
//for(auto it : v) cout << it << " ";
//cout << "\n";
//assert(v.size() == (n - 1));
if(v.size() != (n - 1)) exit(0);
return count_common_roads(v);
}
set<int> Adj[N];
bool vis[N];
int cnt;
int tim[N], low[N];
int edg[N];// backedge that correspond to low
int ind[N][N], dep[N];
bool find[N * N], answ[N * N], bri[N * N];
int par[N];
vector<int> ask;
void dfs(int u, int p){
if((double)clock() / (double)CLOCKS_PER_SEC >= 1.0)) exit(0);
vis[u] = 1;
cnt++;
tim[u] = low[u] = cnt;
edg[u] = -1;
for(auto v : Adj[u]){
if(!vis[v]){
ask.pb(ind[u][v]);
dep[v] = dep[u] + 1;
par[v] = u;
dfs(v, u);
if(low[u] > low[v]){
low[u] = low[v];
edg[u] = edg[v];
}
if(low[v] > tim[u]){
find[ind[u][v]] = answ[ind[u][v]] = bri[ind[u][v]] = 1;
}
}
else if(v != p){
if(low[u] > tim[v]){
low[u] = tim[v];
edg[u] = ind[u][v];
}
}
}
}
vector<int> roads;
bool get(int u, int need){
if((double)clock() / (double)CLOCKS_PER_SEC >= 1.0)) exit(0);
vis[u] = 1;
if(u == need) return 1;
for(auto v : Adj[u]){
if(vis[v]) continue;
if(get(v, need)){
roads.pb(ind[u][v]);
return 1;
}
}
return 0;
}
int save[N];
vector<int> oth;
void find_oth_edg(int u){
if((double)clock() / (double)CLOCKS_PER_SEC >= 1.0)) exit(0);
vis[u] = 1;
for(auto v : Adj[u]){
if(vis[v]) continue;
oth.pb(ind[u][v]);
find_oth_edg(v);
}
}
vector<int> find_roads(int n_, vector<int> u, vector<int> v){
n = n_, m = u.size();
for(int i = 0; i < m; i++){
Adj[u[i]].insert(v[i]);
Adj[v[i]].insert(u[i]);
ind[u[i]][v[i]] = ind[v[i]][u[i]] = i;
}
dfs(0, 0);
for(int i = 0; i < m; i++){
if(bri[i]){
// cout << i << "\n";
Adj[u[i]].erase(v[i]);
Adj[v[i]].erase(u[i]);
}
}
for(int i = 0; i < n; i++) vis[i] = 0;
cnt = 0;
ask.clear();
for(int i = 0; i < n; i++){
if(!vis[i]){
dep[i] = 0;
dfs(i, i);
}
}
for(auto it : ask){
if(find[it]) continue;
int a = u[it], b = v[it];
if(par[b] != a) swap(a, b);
for(int i = 0; i < n; i++) vis[i] = 0;
Adj[a].erase(b), Adj[b].erase(a);
roads.clear();
get(b, a);
roads.pb(it);
// cout << "OK " << it << "\n";
// for(auto it2 : roads) cout << it2 << " ";
// cout << "\n";
for(int i = 0; i < n; i++) vis[i] = 0;
for(int i = 0; i < m; i++){
if(bri[i]){
Adj[u[i]].insert(v[i]);
Adj[v[i]].insert(u[i]);
}
}
for(auto it2 : roads){
vis[u[it2]] = vis[v[it2]] = 1;
}
oth.clear();
// finding other edges apart from the cycle
for(auto it2 : roads){
find_oth_edg(u[it2]);
find_oth_edg(v[it2]);
}
for(auto it2 : roads){
vector<int> askk = oth;
for(auto it3 : roads) if(it2 != it3) askk.pb(it3);
save[it2] = count(askk);
}
int mn = oo, mx = -oo;
for(auto it2 : roads){
mn = min(mn, save[it2]);
mx = max(mx, save[it2]);
}
if(mn == mx){// then everything equals to zero
for(auto it2 : roads){
find[it2] = 1;
answ[it2] = 0;
}
}
else{
for(auto it2 : roads){
find[it2] = 1;
if(save[it2] == mn) answ[it2] = 1;
else answ[it2] = 0;
}
}
for(int i = 0; i < m; i++){
if(bri[i]){
Adj[u[i]].erase(v[i]);
Adj[v[i]].erase(u[i]);
}
}
// assert(par[b] == a);
// int c = u[edg[b]], d = v[edg[b]];
}
for(int i = 0; i < m; i++){
if(bri[i]){
Adj[u[i]].insert(v[i]);
Adj[v[i]].insert(u[i]);
}
}
vector<int> vv = ask;
for(int i = 0; i < m; i++) if(bri[i]) vv.pb(i);
int ori_ans = count(vv);
// for(int i = 0; i < m; i++) cout << find[i] << " " << answ[i] << "\n";
for(int i = 0; i < m; i++){
if(find[i]) continue;
find[i] = 1;
int a = u[i], b = v[i];
if(dep[a] > dep[b]) swap(a, b);
int temp = ind[b][par[b]];
vector<int> vv;
for(int j = 0; j < m; j++) if(bri[j]) vv.pb(j);
for(auto it : ask) if(it != temp) vv.pb(it);
vv.pb(i);
answ[i] = answ[temp] + (count(vv) - ori_ans);
}
vector<int> ans;
for(int i = 0; i < m; i++) if(answ[i]) ans.pb(i);
//assert(ans.size() == (n - 1));
return ans;
}
/*
void process(){
cin >> n;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) process();
}
*/