#include "simurgh.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 500 + 5;
vector<int> adj[maxn];
int par[maxn];
ii e[maxn];
int dep[maxn];
int state[maxn * maxn];
bool used[maxn * maxn];
void dfs(int u , int par){
for(auto & c : adj[u]){
int v = e[c].first + e[c].second - u;
if(v == par)continue;
::par[v] = c;
dep[v] = dep[u] + 1;
dfs(v , u);
}
}
int lab[maxn];
int FindLab(int u){
return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
}
bool Merge(int u , int v , int c){
int s = FindLab(u) , d = FindLab(v);
if(s == d)return 0;
adj[u].pb(c);
adj[v].pb(c);
if(lab[u] > lab[v])swap(u,v);
lab[u] += lab[v];lab[v] = u;
return 1;
}
vector<int> pick(int n , int m){
vector<int> cur;
for(int i = 0 ; i < n ; ++i)lab[i] = -1 , adj[i].clear();
for(int i = 0 ; i < m ; ++i){
if(state[i] == 1){
if(Merge(e[i].first,e[i].second , i))cur.pb(i);
}
}
for(int i = 0 ; i < m ; ++i){
if(state[i] == -1){
if(Merge(e[i].first,e[i].second , i))cur.pb(i);
}
}
for(int i = 0 ; i < m ; ++i)used[i] = 0;
for(auto & c : cur)used[c] = 1;
return cur;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
memset(state,-1,sizeof state);
int m = u.size();
for(int i = 0 ; i < m ; ++i){
e[i] = mp(u[i] , v[i]);
}
auto cur = pick(n , m);
int cur_common = count_common_roads(cur);
dfs(0 , -1);
for(int i = 0 ; i < m ; ++i){
if(used[i] || state[i] == 0)continue;
int u , v;tie(u,v) = e[i];
vector<int> val;
while(u != v){
if(dep[u] < dep[v])swap(u,v);
if(state[par[u]] == -1)val.pb(par[u]);
u = e[par[u]].first + e[par[u]].second - u;
}
if(val.size() == 0)continue;
bool ok = 1;
for(auto & c : val){
cur.erase(find(cur.begin(),cur.end(),c));
cur.pb(i);
int tmp = count_common_roads(cur);
if(tmp > cur_common){
state[i] = 1;
used[i] = 1;
cur_common = tmp;
ok = 0;
// for(int j = 0 ; j < n ; ++j)cout << adj[j].size() << endl;
adj[e[c].first].erase(find(adj[e[c].first].begin() , adj[e[c].first].end(),c));
adj[e[c].second].erase(find(adj[e[c].second].begin() , adj[e[c].second].end(),c));
adj[e[i].first].pb(i);adj[e[i].second].pb(i);
dfs(0,-1);
break;
}else{
cur.pop_back();
cur.pb(c);
}
if(tmp < cur_common){
state[i] = 0;
state[c] = 1;
ok = 0;
break;
}
}
if(ok){
state[i] = 0;
for(auto & c : val)state[c] = 0;
cur = pick(n , m);
dfs(0,-1);
cur_common = count_common_roads(cur);
}
}
return cur;
}
#ifdef LOCAL
#include "simurgh.h"
#include <cstdio>
#include <cassert>
#include <vector>
#include <cstdlib>
#include <string>
using namespace std;
static int MAXQ = 30000;
static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;
static void wrong_answer() {
printf("NO\n");
exit(0);
}
static bool is_valid(const vector<int>& r) {
if(int(r.size()) != n - 1)
return false;
for(int i = 0; i < n - 1; i++)
if (r[i] < 0 || r[i] >= m)
return false;
return true;
}
static int _count_common_roads_internal(const vector<int>& r) {
if(!is_valid(r))
wrong_answer();
int common = 0;
for(int i = 0; i < n - 1; i++) {
bool is_common = goal[r[i]];
if (is_common)
common++;
}
return common;
}
int count_common_roads(const vector<int>& r) {
q++;
if(q > MAXQ)
wrong_answer();
return _count_common_roads_internal(r);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
assert(2 == scanf("%d %d", &n, &m));
u.resize(m);
v.resize(m);
for(int i = 0; i < m; i++)
assert(2 == scanf("%d %d", &u[i], &v[i]));
goal.resize(m, false);
for(int i = 0; i < n - 1; i++) {
int id;
assert(1 == scanf("%d", &id));
goal[id] = true;
}
vector<int> res = find_roads(n, u, v);
if(_count_common_roads_internal(res) != n - 1)
wrong_answer();
printf("YES\n");
return 0;
}
#endif // LOCAL
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
761 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
761 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
761 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1280 KB |
correct |
| 2 |
Incorrect |
1 ms |
1280 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
761 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
