제출 #333437

#제출 시각아이디문제언어결과실행 시간메모리
333437Ahmad_HasanProsjecni (COCI16_prosjecni)C++17
24 / 120
1 ms364 KiB
#include <bits/stdc++.h> using namespace std; //////////////////////LCA////////////////////////////// struct LCA{ int n,rot; int sz=2; vector<vector<int> >adj; vector<int> hights; vector<int> eclid; vector<int> tree; vector<int> vis; vector<int> frst; LCA(vector<vector<int> >&padj,int prot,int pnods){ adj=padj; n=pnods; rot=prot; vis.resize(n+5); frst.resize(n+5); hights=vector<int>(n+5,INT_MAX); dfs(rot); initree(); } void dfs(int rott,int h=0){ if(vis[rott]) return; vis[rott]=1; frst[rott]=eclid.size(); eclid.push_back(rott); hights[rott]=h; for(int i=0;i<adj[rott].size();i++){ if(vis[adj[rott][i]] )continue; dfs(adj[rott][i],h+1); eclid.push_back(rott); } } void initree(){ while(sz<=eclid.size()) sz*=2; tree.resize(2*sz); for(int i=0;i<eclid.size();i++){ update(i,eclid[i]); } } void update(int i,int val,int x,int l,int r){ if(i<l||i>r) return; if(l==r) { tree[x]=val; return; } int mid=(l+r)/2; update(i,val,2*x,l,mid); update(i,val,2*x+1,mid+1,r); tree[x]=(hights[tree[2*x]]<=hights[tree[2*x+1]])?tree[2*x]:tree[2*x+1]; } void update(int i,int val){ update(i,val,1,0,sz-1); } int get(int l,int r,int x,int lx,int rx){ if(r<lx||l>rx) return n; if(lx>=l&&rx<=r) return tree[x]; int mid=(lx+rx)/2; int ret1=get(l,r,2*x,lx,mid); int ret2=get(l,r,2*x+1,mid+1,rx); return (hights[ret1]<=hights[ret2])? ret1:ret2; } int get(int l,int r){ return get(l,r,1,0,sz-1); } int gethight(int nd){ return hights[nd]; } int fndlca(int x,int y){ if(frst[x]>frst[y]) swap(x,y); return get(frst[x],frst[y]); } void print(){ for(int i=0;i<eclid.size();i++){ cout<<eclid[i]<<' '; } cout<<'\n'; for(int i=0;i<frst.size();i++){ cout<<frst[i]<<' '; } cout<<'\n'; } }; struct edge{ int f,t,w; edge(int f,int t,int w):f(f),t(t),w(w){}; bool operator <(const edge &e)const{ return w>e.w; } }; //////////////////////////Dijkestra//////////////////////////////////// vector<vector<edge> >eadj; vector<int> dijk(int n,int rot=0){ vector<int>dists(n+5,INT_MAX); priority_queue<edge>pq; pq.push(edge(-1,0,0)); while(pq.size()){ edge cr=pq.top(); pq.pop(); if(dists[cr.t]!=INT_MAX) continue; dists[cr.t]=cr.w; for(int i=0;i<eadj[cr.t].size();i++){ pq.push(edge(cr.t,eadj[cr.t][i].t,cr.w+eadj[cr.t][i].w)); } } return dists; } vector<vector<int> >adj; vector<long double>ews;/** vector<int>vis; int dfs1(int cr,int dis,int ttl=0){ if(cr==dis){ return ttl; } vis[cr]=1; int ret=INT_MAX; for(int i=0;i<adj[cr].size();i++){ if(!vis[adj[cr][i]]) ret=min(ret,dfs1(adj[cr][i],dis,ttl+1)); } vis[cr]=0; return ret; } int dfs2(int cr,int dis,int sh,int ttl=0){ if(cr==dis){ return ttl==sh; } vis[cr]=1; int ret=0; for(int i=0;i<adj[cr].size();i++){ if(!vis[adj[cr][i]]) ret=(ret+dfs2(adj[cr][i],dis,sh,ttl+1)); } vis[cr]=0; return ret; } int dfs3(int cr,int dis,int sh,int ttlsh,int ttl=0){ if(cr==dis){ int ret=(ttl==sh); ews[cr]+=(long double)ret/(long double)ttlsh; return ret; } vis[cr]=1; int ret=0; for(int i=0;i<adj[cr].size();i++){ if(!vis[adj[cr][i]]) ret=(ret+dfs3(adj[cr][i],dis,sh,ttlsh,ttl+1)); } vis[cr]=0; ews[cr]+=(long double)ret/(long double)ttlsh; return ret; } */ void BFS(int from,int to,int n){ vector<int>pths(n+5),hits(n+5),vis(n+5); vector<int>pths2(n+5),hits2(n+5),vis2(n+5); vector<int>pths3(n+5),vis3(n+5); queue<int>iq,iq2,iq3; iq.push(from); pths[from]=1; hits[from]=0; int crh=0; int fnd=0; while(!fnd&&iq.size()){ int sz=iq.size(); while(sz--){ int cr=iq.front(); iq.pop(); ///cout<<cr<<' '<<hits[cr]<<'\n'; if(vis[cr]){ continue; } vis[cr]=1; if(cr==to){ fnd=1; break; } for(int i=0;i<adj[cr].size();i++){ if(hits[adj[cr][i]]==crh+1||(hits[adj[cr][i]]==0&&adj[cr][i]!=from)){ pths[adj[cr][i]]+=pths[cr]; hits[adj[cr][i]]=crh+1; iq.push(adj[cr][i]); } } } crh++; } int ttlsh=pths[to]; int sh=hits[to]; iq2.push(to); pths2[to]=1; hits2[to]=0; crh=0; fnd=0; while(!fnd&&iq2.size()){ int sz=iq2.size(); while(sz--){ int cr=iq2.front(); iq2.pop(); if(vis2[cr]){ continue; } vis2[cr]=1; if(cr==from){ fnd=1; break; } for(int i=0;i<adj[cr].size();i++){ if(hits2[adj[cr][i]]==crh+1||(hits2[adj[cr][i]]==0&&adj[cr][i]!=to)){ pths2[adj[cr][i]]+=pths2[cr]; hits2[adj[cr][i]]=crh+1; iq2.push(adj[cr][i]); } } } crh++; } vis2[from]=vis2[to]=vis[from]=vis[to]=1; vector<int>rch(n+5); for(int i=0;i<n;i++){ ///cout<<hits[i]<<'-'<<hits2[i]<<' '; if(hits[i]==sh-hits2[i]&&vis2[i]&&vis[i]){ rch[i]=1; } } ///cout<<'\n'; iq3.push(to); crh=0; fnd=0; while(!fnd&&iq3.size()){ int sz=iq3.size(); while(sz--){ int cr=iq3.front(); iq3.pop(); if(vis3[cr]){ continue; } vis3[cr]=1; if(cr==from){ fnd=1; break; } int ttl=0; for(int i=0;i<adj[cr].size();i++){ if(hits2[adj[cr][i]]==crh+1&&rch[adj[cr][i]]){ ttl++; } iq3.push(adj[cr][i]); } pths3[cr]=pths2[cr]*ttl; } crh++; } pths3[to]=pths3[from]=ttlsh; for(int i=0;i<n;i++){ ///cout<<pths3[i]<<'-'<<pths2[i]<<' '; if(rch[i]){ ews[i]+=(long double)pths3[i]/(long double)ttlsh; } } ///cout<<'\n'; } int main() { /**ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);*/ int n; cin>>n; if(n%2==0){ cout<<-1<<'\n'; return 0; } for(int i=1;i<=n*n;i++){ cout<<i<<' '; if(i%n==0) cout<<'\n'; } return 0; } /*** 6 5 0 2 1 2 2 3 3 4 3 5 2 0 5 1 4 5 4 0 1 1 2 2 3 3 4 1 3 4 15 19 0 3 1 3 1 4 1 5 2 5 3 6 3 7 4 7 5 7 6 10 7 9 7 10 7 11 8 11 9 12 9 13 10 13 11 13 11 14 2 4 10 3 8 6 9 0 1 0 2 0 3 1 2 2 3 1 4 3 4 4 5 2 4 2 0 4 0 5 */

컴파일 시 표준 에러 (stderr) 메시지

prosjecni.cpp: In member function 'void LCA::dfs(int, int)':
prosjecni.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i=0;i<adj[rott].size();i++){
      |                     ~^~~~~~~~~~~~~~~~~
prosjecni.cpp: In member function 'void LCA::initree()':
prosjecni.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while(sz<=eclid.size()) sz*=2;
      |               ~~^~~~~~~~~~~~~~
prosjecni.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int i=0;i<eclid.size();i++){
      |                     ~^~~~~~~~~~~~~
prosjecni.cpp: In member function 'void LCA::print()':
prosjecni.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int i=0;i<eclid.size();i++){
      |                     ~^~~~~~~~~~~~~
prosjecni.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int i=0;i<frst.size();i++){
      |                     ~^~~~~~~~~~~~
prosjecni.cpp: In function 'std::vector<int> dijk(int, int)':
prosjecni.cpp:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for(int i=0;i<eadj[cr.t].size();i++){
      |                     ~^~~~~~~~~~~~~~~~~~
prosjecni.cpp: In function 'void BFS(int, int, int)':
prosjecni.cpp:218:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |             for(int i=0;i<adj[cr].size();i++){
      |                         ~^~~~~~~~~~~~~~~
prosjecni.cpp:247:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |             for(int i=0;i<adj[cr].size();i++){
      |                         ~^~~~~~~~~~~~~~~
prosjecni.cpp:283:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  283 |             for(int i=0;i<adj[cr].size();i++){
      |                         ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...