| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 949719 |
2024-03-19T15:25:33 Z |
qin |
Simurgh (IOI17_simurgh) |
C++17 |
|
70 ms |
25312 KB |
#include <bits/stdc++.h>
#include "simurgh.h"
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
struct graph{
vv<vv<pii>> g;
vv<int> vis;
vv<vv<int>> queries;
vv<int> res, taken;
vv<int> av;
void init(int n, int m){
g.resize(n), vis.resize(n); // trzeba pamietać, że są indeksowane od 0 do n-1 !!!
queries.resize(m), res.resize(m, -1), taken.resize(m, 0), av.resize(m);
}
void add_edge(int a, int b, int i){ g[a].emplace_back(b, i), g[b].emplace_back(a, i); }
void dfs(int x, int c, vv<int> &edges){
vis[x] = c;
for(pii &u : g[x]) if(!vis[u.fi]) edges.emplace_back(u.se), dfs(u.fi, c, edges);
}
vv<int> prep_colour(int x, int &c){
int l = 0; fill(all(vis), 0);
vis[x] = inf;
vv<int> edges;
for(pii &u : g[x]) if(!vis[u.fi]) dfs(u.fi, ++l, edges);
c = l;
return edges;
}
void dfs_check(int x){
vis[x] = 1;
for(pii &u : g[x]) if(!vis[u.fi] && av[u.se]) dfs_check(u.fi);
}
bool check_tree(vv<int> tmp){
fill(all(av), 0), fill(all(vis), 0);
bool ret = 1;
if(ssize(tmp) != ssize(g)-1) ret = 0;
for(int u : tmp) av[u] = 1;
dfs_check(0);
for(int u : vis) if(!u) ret = 0;
return ret;
}
vv<int> get_roads(){
int n = ssize(g);
for(int i = 0; i < n; ++i){
int k = 0;
vv<int> edges = prep_colour(i, k);
vv<vv<int>> t(k+1);
for(pii &u : g[i]) t[vis[u.fi]].emplace_back(u.se);
for(int j = 1; j <= k; ++j){
int mx = -1, id = 0;
for(int u : t[j]) if(taken[u]) mx = res[u], id = u;
vv<int> equal_to_max;
for(int u : t[j]) if(res[u] == -1 || u == id){
vv<int> tmp = edges;
for(int l = 1; l <= k; ++l) if(l != j) tmp.emplace_back(t[l].back());
tmp.emplace_back(u);
//~ assert(ssize(tmp) == ssize(g)-1);
//~ printf("a %d %d %d\n", i, j, u);
//~ for(int u : tmp) printf("%d ", u);
//~ pn;
//~ assert(check_tree(tmp));
int ask = count_common_roads(tmp);
if(ask > mx) equal_to_max.clear();
if(ask >= mx) mx = ask, equal_to_max.emplace_back(u);
tmp.pop_back(), queries[u] = tmp, res[u] = ask;
}
for(int u : equal_to_max) taken[u] = 1;
}
}
vv<int> result;
for(int i = 0; i < ssize(taken); ++i) if(taken[i]) result.emplace_back(i);//, printf("%d\n", i);
//~ assert(ssize(result) == ssize(g)-1);
return result;
}
};
vv<int> find_roads(int n, vv<int> u, vv<int> v){
graph g; g.init(n, ssize(u));
for(int i = 0; i < ssize(u); ++i) g.add_edge(u[i], v[i], i);
return g.get_roads();
}
#ifdef LOCAL
int main(){
int T = 1;
for(++T; --T; ) answer();
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
correct |
| 2 |
Correct |
1 ms |
348 KB |
correct |
| 3 |
Incorrect |
70 ms |
25312 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
