| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 333437 | Ahmad_Hasan | Prosjecni (COCI16_prosjecni) | C++17 | 1 ms | 364 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||