| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 901089 | nightfal | Wiring (IOI17_wiring) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;
void printAdjMatrix(vector<vector<int>>& adjM) {
int n = adjM.size();
for(int i=0; i<n; i++) {
printf("%d:",i);
for(int elem: adjM[i])
printf(" %d",elem);
printf("\n");
}
}
void printAdjList(vector<vector<int>>& adjL) {
int n = adjL.size();
for(int i=0; i<n; i++) {
printf("%d:",i);
for(int elem: adjL[i])
printf(" %d", elem);
printf("\n");
}
}
void printDegree(vector<int>& Deg) {
int n = Deg.size();
for(int i=0; i<n; i++) printf("Deg[%d]=%d ",i,Deg[i]);
printf("\n");
}
bool isSubtask1(vector<int>& u, vector<int>& v) {
int m = u.size();
for(int i=0; i<m; i++)
if (v[i]!=u[i] && v[i]!=u[i]+1) return false;
return true;
}
bool isSubtask2(const int n) { return n <= 15;}
bool dfs(int now, int dest, vector<int>& a, vector<int>& r, vector<vector<int>>& adjL, vector<bool>& dis/*, vector<int>& fin*/, vector<int>& ans, int& cnt) {
printf("now:%d, dest:%d\n",now,dest);
if (dis[now]) return r[now] || ans[now];
// else dis[now]=++cnt;
else dis[now] = true;
if (now==dest) return true;
if (a[now]) {
for(int i=0; i<adjL[now].size(); i++)
if(dfs(i,dest,a,r,adjL,dis/*,fin*/,ans,cnt)) {ans[now]=1; break;}
}
else {
int i;
for(i=0; i<adjL[now].size(); i++)
if(!dfs(i,dest,a,r,adjL,dis/*,fin*/,ans,cnt)) break;
if (i==adjL[now].size()) ans[now] = 1;
}
if (ans[now]) printf("win %d \n",now);
return ans[now];
}
bool dfs2(int src, vector<int>& a, vector<int>&r, vector<vector<int>>& adjL, vector<int>& ans) {
return true;
}
vector<int> subtask2(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
int n=a.size(), m=u.size();
// queue<int> q;
vector<vector<int>> adjL(n), adjLRev(n), adjM(n,vector<int>(n));
vector<int> inDeg(n), outDeg(n);
for(int i=0; i<m; i++) {
adjL[u[i]].push_back(v[i]); adjLRev[v[i]].push_back(u[i]);
adjM[u[i]][v[i]] = 1;
inDeg[v[i]]++; outDeg[u[i]]++;
}
for(auto& list: adjL) sort(list.begin(),list.end());
for(auto& list: adjLRev) sort(list.begin(),list.end());
printf("Adjacency Matrix\n"); printAdjMatrix(adjM);
printf("Adjacency List\n"); printAdjList(adjL);
printf("Adjacency List Reverse\n"); printAdjList(adjLRev);
printf("outDegree\n"); printDegree(outDeg);
printf("inDegree\n"); printDegree(inDeg);
vector<int> ans(n);
for(int i=0; i<n; i++)
if(r[i]==1) {
vector<bool> dis(n,false)/*, fin(n,0) */; int cnt=0, j;
// dis[i] = ++cnt;
dis[i] = true;
if(a[i]) {
for(j=0; j<adjL[i].size(); j++)
if(dfs(j,i,a,r,adjL,dis/*,fin*/,ans,cnt)) break;
if (j!=adjL[i].size()) ans[i] = 1;
}
else {
for(j=0; j<adjL[i].size(); j++)
if(!dfs(j,i,a,r,adjL,dis/*,fin*/,ans,cnt)) break;
if (j==adjL[i].size()) ans[i] = 1;
}
if (ans[i]) printf("win %d \n",i);
// fin[i] = ++cnt;
}
// for(int i=0; i<n; i++) if (ans[i]==0) ans[i] = dfs2(i,a,r,adjL,ans);
return ans;
}
vector<int> subtask1(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
int n = a.size(), m = u.size();
vector<int> ans(n,0);
vector<vector<int>> adj(n,vector<int>(n,0));
for(int i=0; i<m; i++) adj[u[i]][v[i]] = 1;
ans[n-1]=r[n-1];
for(int i=n-2; i>=0; i--)
if (a[i]) {ans[i] = adj[i][i] && r[i] || adj[i][i+1] && ans[i+1];}
else {ans[i] = (adj[i][i]==0 || r[i]) && (adj[i][i+1]==0 || ans[i+1]);}
return ans;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
vector<int> res(a.size());
int n = a.size(), m = u.size();
vector<vector<int>> adj(n);
for(int i=0; i<m; i++) adj[u[i]].push_back(v[i]);
for(int i=0; i<n; i++) sort(adj[i].begin(),adj[i].end());
if (isSubtask2(n)) return subtask2(a,r,u,v);
if (isSubtask1(u,v)) return subtask1(a,r,u,v);
for(int i=0; i<n; i++) {
cout << i << ": ";
for (const int elem: adj[i])
cout << elem << " ";
cout << endl;
}
for(int i = 0; i < n; i++)
res[i] = i % 2;
return res;
}