Submission #243423

#TimeUsernameProblemLanguageResultExecution timeMemory
243423crossing0verSimurgh (IOI17_simurgh)C++17
0 / 100
5 ms640 KiB
#include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define vi vector<int> #define pii pair<int,int> #include "simurgh.h" using namespace std; int n,m; vi u,v,adj[505]; bool good[25500],vis[505]; // if good[i] = 1, edge[u[i]v[i] ] = good int type[25500]; map<pii,int> id; set<int> query; int tin[505],tout[505],timer,w[505],P[505],num; ////////////// int ask() { vi v; for (int i : query) v.pb(i); int x = count_common_roads(v); return x; } ////////////// void erase(int a,int b) { query.erase(id[{a,b}]); } void insert(int a,int b) { query.insert(id[{a,b}]); } /////////////// void jartidfs(int v) { vis[v] = 1; for (int i : adj[v]) { if (!vis[i]) { insert(v,i); jartidfs(i); } } } void dfs(int v,int p) { int z = 0; P[v] = p; vi parents,erased; if (p != -1) parents.pb(p); vis[v] = 1; tin[v] = w[v] = z = ++timer; for (int i : adj[v]) { if (i == p) continue; if (vis[i]) { z = min(z,tin[i]); parents.pb(i); } else { dfs(i,v); w[v] = min(w[v],w[i]); } } vector<pii> dif,same; set <int> good,bad; sort(parents.begin(),parents.end(),[&](int i,int j) { return tin[i] > tin[j]; }); for (int i = 1; i < parents.size();i++) { int cnt = num; int curnode = v; insert(v,parents[i]); P[v] = parents[i-1]; int id2 = id[{v,parents[i]}]; do{ erase(curnode,P[curnode]); num = ask(); int id1 = id[{curnode,P[curnode]}]; if (cnt < num) { good.insert(id1); bad.insert(id2); } else if (cnt > num) { bad.insert(id2); good.insert(id2); } else { same.pb({id1,id2}); } if (P[curnode != parents[i]]) insert(curnode,P[curnode]); else erased.pb(id[{curnode,parents[i]}]); curnode = P[curnode]; }while(curnode != parents[i]); //query.erase(id[{parents[i-1],v}]); //query.insert(id[{parents[i],v}]); //num = ask(); //if (num) } if (parents.size() >= 2) erase(v,parents.back()); for (int i : erased) query.insert(i); vi seen(505); vector<vi> e(505); for (auto i : same) { e[i.fi].pb(i.se); e[i.se].pb(i.fi); } for (int i : good) { queue<int> q; type[i] = 1; seen[i] = 1; q.push(i); while(!q.empty()) { int v = q.front(); q.pop(); for (int j : e[i]) { if (seen[j]) continue; seen[j] = 1; q.push(j); } } } for (int i : bad) { queue<int> q; type[i] = -1; seen[i] = 1; q.push(i); while(!q.empty()) { int v = q.front(); q.pop(); for (int j : e[i]) { if (seen[j]) continue; seen[j] = -1; q.push(j); } } } if (good.empty() && bad.empty() && w[v] <= tin[v]) for (int i : parents) type[id[{v,i}]] = 1; for (int i = v; i != parents.back(); i = P[v]) { type[id[{i,P[i]}]] = 1; } w[v] = min(w[v],z); P[v] = p; } void preprocess(int n1,vi u1, vi v1) { m = u1.size(); n = n1; u = u1; v = v1; for (int i = 0; i < m; i++) { id[{u[i],v[i]}] = id[{v[i],u[i]}] = i; adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]); } } vi find_roads(int n1, vi u1, vi v1) { preprocess(n1,u1,v1); jartidfs(0); num = ask(); memset(vis,0,sizeof vis); dfs(0,-1); // vi ans(n - 1); //int common = count_common_roads(r); // if(common == n - 1) // return r; // r[0] = n - 1; vi ans; for (int i = 0; i < m; i++) if (type[i] == 1) ans.pb(i); ans.resize(n-1); return ans; } /* main() { int n,m; cin >> n >> m; vi u,v; for (int i = 0;i < m ;i++ ) { int a, b; cin >> a >> b; u.pb(a); v.pb(b); } }*/

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < parents.size();i++) {
                  ~~^~~~~~~~~~~~~~~~
simurgh.cpp:109:8: warning: unused variable 'v' [-Wunused-variable]
    int v = q.front();
        ^
simurgh.cpp:124:8: warning: unused variable 'v' [-Wunused-variable]
    int v = q.front();
        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...