Submission #901332

#	Time	Username	Problem	Language	Result	Execution time	Memory
901332		nightfal	Toy Train (IOI17_train)	C++14	5 / 100	47 ms	99020 KiB

train

#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<int>& dis, vector<int>& ans, int& cnt) {
    // printf("now:%d, dest:%d, dis[%d]=%d, r[%d]=%d, ans[%d]=%d\n",now,dest,now,(int) dis[now],now,r[now],now,ans[now]);
    if (dis[now]) return r[now] || ans[now];
    // else dis[now]=++cnt;
    else dis[now] = 1;
    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,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,ans,cnt)) break;
        if (i==adjL[now].size()) ans[now] = 1;
    }
    // if (ans[now]) printf("win %d \n",now);
    return ans[now];
}

void checkNeighbor(int now, vector<int>& a, vector<vector<int>>& adjL, vector<int>& ans) {
    if (a[now]) {
        for(int i=0; i<adjL[now].size(); i++)
            if(ans[adjL[now][i]]) ans[now]=1;
    }
    else {
        int i;
        for(i=0; i<adjL[now].size(); i++)
            if(!ans[adjL[now][i]]) break;
        if (i==adjL[now].size()) ans[now] = 1;
    }
}

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<int> dis(n); int cnt=0, j;
            dis[i] = 1;
            if(a[i]) {
                for(j=0; j<adjL[i].size(); j++) 
                    if(dfs(adjL[i][j],i,a,r,adjL,dis,ans,cnt)) break;
                if (j!=adjL[i].size()) {ans[i] = 1; /*printf("ans[%d]=%d\n",i,ans[i]);*/}
            }
            else {
                for(j=0; j<adjL[i].size(); j++) 
                    if(!dfs(adjL[i][j],i,a,r,adjL,dis,ans,cnt)) break;
                if (j==adjL[i].size()) {ans[i] = 1; /* printf("ans[%d]=%d\n",i,ans[i]);*/}
            }
            // if (ans[i]) printf("win %d \n",i);
        }

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if (ans[j]==0) checkNeighbor(j,a,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;
}

Compilation message (stderr)

train.cpp: In function 'bool dfs(int, int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&, int&)':
train.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i=0; i<adjL[now].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~
train.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(i=0; i<adjL[now].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~
train.cpp:59:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         if (i==adjL[now].size()) ans[now] = 1;
      |             ~^~~~~~~~~~~~~~~~~~
train.cpp: In function 'void checkNeighbor(int, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<int>&)':
train.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i=0; i<adjL[now].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~
train.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(i=0; i<adjL[now].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~
train.cpp:74:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if (i==adjL[now].size()) ans[now] = 1;
      |             ~^~~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> subtask2(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                 for(j=0; j<adjL[i].size(); j++)
      |                          ~^~~~~~~~~~~~~~~
train.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 if (j!=adjL[i].size()) {ans[i] = 1; /*printf("ans[%d]=%d\n",i,ans[i]);*/}
      |                     ~^~~~~~~~~~~~~~~~
train.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |                 for(j=0; j<adjL[i].size(); j++)
      |                          ~^~~~~~~~~~~~~~~
train.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 if (j==adjL[i].size()) {ans[i] = 1; /* printf("ans[%d]=%d\n",i,ans[i]);*/}
      |                     ~^~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> subtask1(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:132:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  132 |         if (a[i]) {ans[i] = adj[i][i] && r[i] || adj[i][i+1] && ans[i+1];}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51