Submission #877257

#TimeUsernameProblemLanguageResultExecution timeMemory
877257nnhzzzRigged Roads (NOI19_riggedroads)C++14
100 / 100
263 ms51604 KiB
// cre: Nguyen Ngoc Hung - Go Go VOI 2024 :> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <unordered_set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #include <cstring> #include <unordered_map> #include <cmath> #include <array> #include <cassert> #include <random> #include <chrono> using namespace std; #define __nnhzzz__ signed main() #define BIT(i,j) ((i>>j)&1LL) #define MASK(i) (1LL<<i) #define ALL(x) (x).begin(),(x).end() #define SZ(x) (int)(x).size() #define PB push_back #define fi first #define se second #define ll long long #define ld long double #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define pii pair<int,int> #define vpii vector<pii> #define vvpii vector<vpii> #define REPDIS(i,be,en,j) for(int i = (be); i<=(en); i+=j) #define REPD(i,be,en) for(int i = (be); i>=(en); --i) #define REP(i,be,en) for(int i = (be); i<=(en); ++i) #define endl "\n" // #define int ll //------------------------------------------------------------------------------------------------// int readInt(){ char c; do{ c = getchar(); }while(c!='-' && !isdigit(c)); bool neg = (c=='-'); int res = neg?0:c-'0'; while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0'); return neg?-res:res; } //------------------------------------------------------------------------------------------------// const int oo = 1e9,LOG = 20,MAXN = 5e5+7,N = 1e2+3; const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353; const ld EPS = 1e-9,PI = acos(-1); //------------------------------------------------------------------------------------------------// template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;} template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;} template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; } template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; } //------------------------------------------------------------------------------------------------// /* ---------------------------------------------------------------- END OF TEMPLATE ---------------------------------------------------------------- Nguyen Ngoc Hung - nnhzzz Training for VOI24 gold medal ---------------------------------------------------------------- */ struct DSU{ vi par; int n; int find(int u){ return u==par[u]?u:par[u]=find(par[u]); } bool same(int u, int v){ return find(u)==find(v); } bool unite(int u, int v){ u = find(u); v = find(v); if(u==v) return false; par[v] = u; return true; } DSU(int _n):n(_n){ par.resize(n+3); iota(ALL(par),0); } }; struct edge{ int u,v,w,id; bool operator < (const edge &other) const { return w<other.w; } }; int ok[MAXN],vis[MAXN],s[MAXN],h[MAXN],p[MAXN],pe[MAXN],t[MAXN]; vector<edge> edges; vpii adj[MAXN]; vi now,nho; int n,m; int find(int u){ return s[u]<0?u:s[u]=find(s[u]); } void unite(int u, int v){ if(s[u]>s[v]) swap(u,v); if(u!=v){ if(h[t[u]]>h[t[v]]) t[u] = t[v]; s[u] += s[v]; s[v] = u; } } void dfs(int u, int par, int dep, int e){ h[u] = dep; p[u] = par; pe[u] = e; for(auto &[v,id]:adj[u]){ if(v==par) continue; dfs(v,u,dep+1,id); } } void sub1(){ vi perm(m),res(m); iota(ALL(perm),0); iota(ALL(res),n); do{ vector<edge> now = edges; REP(i,0,m-1) now[i].w = perm[i]+1; sort(ALL(now)); DSU dsu(n); int flag = 1; REP(i,0,m-1){ if(dsu.unite(now[i].u,now[i].v)){ if(ok[now[i].id]==0){ flag = 0; break; } } } if(flag) mini(res,perm); }while(next_permutation(ALL(perm))); for(auto &i:res) cout << i+1 << " "; } void sub5(){ int cnt = 0; vi res; REP(i,1,m){ if(ok[i]==0){ res.push_back(m); continue; } res.push_back(++cnt); } for(auto &i:res) cout << i << " "; } void sub7(){ dfs(1,0,0,0); REP(i,1,n){ s[i] = -1; t[i] = i; } vi res(m+1,0); int j = 1; REP(i,1,m){ int u = find(edges[i-1].u),v = find(edges[i-1].v); if(ok[i]==1 && res[i]==0){ res[i] = j++; unite(u,v); } if(res[i]!=0) continue; // edge i - not mst vi tmp; while(u!=v){ if(h[t[u]]<h[t[v]]) swap(u,v); tmp.push_back(pe[t[u]]); unite(u,find(p[t[u]])); u = find(u); v = find(v); } sort(ALL(tmp)); for(auto &x:tmp) res[x] = j++; res[i] = j++; } REP(i,1,m) cout << res[i] << " "; } /* 6 6 1 4 1 2 2 3 4 5 3 4 5 6 2 3 4 5 6 */ void solve(){ cin >> n >> m; int s5 = 1; REP(i,1,m){ int u,v; cin >> u >> v; edges.push_back({u,v,0,i}); if(u!=i || v!=i%n+1) s5 = 0; } REP(i,1,n-1){ int x; cin >> x; ok[x] = 1; adj[edges[x-1].u].emplace_back(edges[x-1].v,x); adj[edges[x-1].v].emplace_back(edges[x-1].u,x); } sub7(); return ; if(n<=9 && m<=9){ sub1(); return ; } if(s5 && n==m){ sub5(); return ; } sub7(); } __nnhzzz__{ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "test" if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } #define task1 "ZONING" if(fopen(task1".inp","r")){ freopen(task1".inp","r",stdin); freopen(task1".out","w",stdout); } int test = 1; while(test--){ solve(); } cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n"; return 0; } /** /\_/\ * (= ._.) * / >TL \>AC **/

Compilation message (stderr)

riggedroads.cpp: In function 'void dfs(int, int, int, int)':
riggedroads.cpp:153:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |  for(auto &[v,id]:adj[u]){
      |            ^
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:265:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  265 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:266:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  266 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:270:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  270 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:271:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  271 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...